Approximation algorithm for steiner tree problem with neighbor-induced cost
Journal of the Operations Research Society of Japan(2023)
摘要
The Steiner tree problem is one of the most fundamental combinatorial optimization problems. In this problem, the input is an undirected graph, a cost function on the edge set, and a subset of vertices called terminals, and the objective is to find a minimum-cost tree spanning all the terminals. By changing the objective function, several variants of the Steiner tree problem have been studied in the literature. For example, in the min-power version of the problem, the goal is to find a Steiner tree S minimizing the total power consumption of vertices, where the power of a vertex v is the maximum cost of any edge of Sincident to v. Another example is the node-weighted version of the problem, in which costs are assigned to vertices instead of edges. In this paper, we introduce a common generalization of these variants and give an approximation algorithm for it. When the maximum degree Δ of the input graph is constant, our algorithm runs in polynomial time and the approximation ratio is 2.016 + ln Δ.
更多查看译文
关键词
steiner tree problem,approximation,algorithm,neighbor-induced
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要