A partition-based relaxation for Steiner trees
A partition-based relaxation for Steiner trees
复制标题
基于分区的 Steiner 树松弛
作者：
J. Könemann;David Pritchard;Kunlun Tan
Steiner树问题是一个经典的NP难优化问题，具有广泛的实际应用。在此问题的一个实例中，我们给出一个无向图 G = (V, E)、一组终结点$${Rsubseteq V}$$ 以及所有边 $${e in E}$$ 的非负成本 ce 。任何包含所有终结点的树称为 Steiner 树；目标是找到成本最低的斯坦纳树。顶点 $${V ackslash R}$$ 称为 Steiner 顶点。对于 Steiner 树问题，已知的最佳近似算法是 Robins 和 Zelikovsky 提出的贪婪算法（SIAM J Discrete Math 19(1):122–134, 2005）；它实现了 $${1+frac{ln 3}{2}大约 1.55}$$ 的性能保证。另一方面，最著名的基于线性规划 (LP) 的算法源自 Goemans 和 Bertsimas（Math Program 60:145–166, 1993），并实现了 2−2/|R| 的近似比。在本文中，我们通过证明 Robins 和 Zelikovsky 的算法可以被视为关于新颖的 LP 松弛的迭代原始对偶算法，在贪婪方法和基于 LP 的方法之间建立了联系。第一次迭代中使用的 LP 比众所周知的双向切割松弛更强。如果 $${G ackslash R}$$ 的每个连通分量至多有 b 个顶点，则实例是 b 准二分的。我们证明，在这种情况下，Robins 和 Zelikovsky 的算法具有比 $${1+frac{ln 3}{2}}$$ 更好的近似率，并且我们证明了 LP 的完整性差距在 $${frac{8}{7}}$$ 和 $${frac{2b+1}{b+1}}$$ 之间。
The Steiner tree problem is a classical NP-hard optimization problem with a wide range of practical applications. In an instance of this problem, we are given an undirected graph G = (V, E), a set of terminals$${Rsubseteq V}$$ , and non-negative costs ce for all edges $${e in E}$$ . Any tree that contains all terminals is called a Steiner tree; the goal is to find a minimum-cost Steiner tree. The vertices $${V ackslash R}$$ are called Steiner vertices. The best approximation algorithm known for the Steiner tree problem is a greedy algorithm due to Robins and Zelikovsky (SIAM J Discrete Math 19(1):122–134, 2005); it achieves a performance guarantee of $${1+frac{ln 3}{2}approx 1.55}$$ . The best known linear programming (LP)-based algorithm, on the other hand, is due to Goemans and Bertsimas (Math Program 60:145–166, 1993) and achieves an approximation ratio of 2−2/|R|. In this paper we establish a link between greedy and LP-based approaches by showing that Robins and Zelikovsky’s algorithm can be viewed as an iterated primal-dual algorithm with respect to a novel LP relaxation. The LP used in the first iteration is stronger than the well-known bidirected cut relaxation. An instance is b-quasi-bipartite if each connected component of $${G ackslash R}$$ has at most b vertices. We show that Robins’ and Zelikovsky’s algorithm has an approximation ratio better than $${1+frac{ln 3}{2}}$$ for such instances, and we prove that the integrality gap of our LP is between $${frac{8}{7}}$$ and $${frac{2b+1}{b+1}}$$ .