Steiner Tree 1.39-Approximation in Practice
Steiner Tree 1.39-Approximation in Practice
复制标题
Steiner 树 1 39 实践中的近似
DOI：
10.1007/978-3-319-14896-0_6
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
M. Chimani
中科院分区：
文献类型：
--
作者：
S. Beyer;M. Chimani
我们考虑目前最强的Steiner树近似算法，该算法最近由Goemans， Olver， Rothvoß和Zenklusen（2012）发表。首先求解一个超图LP松弛问题，然后应用拟阵理论得到一个积分解。所得到的斯坦纳树的代价最多是最优斯坦纳树代价的两倍，在最优斯坦纳树的代价中，当某个参数趋于无穷时，最优斯坦纳树的代价趋于零。然而，多项式运行时间的程度取决于这个常数，所以在实践中只有小是可处理的。据我们所知，该算法尚未在实践中实现和评估。我们研究了算法的不同实现方面和参数选择，并将调整后的变体与精确的基于lp的算法以及快速和简单的近似进行了比较。
We consider the currently strongest Steiner tree approximation algorithm that has recently been published by Goemans, Olver, Rothvoß and Zenklusen (2012). It first solves a hypergraphic LP relaxation and then applies matroid theory to obtain an integral solution. The cost of the resulting Steiner tree is at most-times the cost of an optimal Steiner tree wheretends to zero as some parametertends to infinity. However, the degree of the polynomial running time depends on this constant, so only smallare tractable in practice.The algorithm has, to our knowledge, not been implemented and evaluated in practice before. We investigate different implementation aspects and parameter choices of the algorithm and compare tuned variants to an exact LP-based algorithm as well as to fast and simple-approximations.
登录
查看更多内容
实践中基于收缩的斯坦纳树近似
DOI：
10.1007/978-3-642-25591-5_6
发表时间：
2011
期刊：
影响因子：
--
作者：
M. Chimani;M. Woste
通讯作者：
M. Woste
超图斯坦纳树松弛的拟阵和完整性差距
DOI：
10.1145/2213977.2214081
发表时间：
2011
期刊：
ArXiv
影响因子：
--
作者：
M. Goemans;Neil Olver;T. Rothvoss;R. Zenklusen
通讯作者：
R. Zenklusen
超图中的生成树及其在斯坦纳树中的应用
DOI：
10.18130/v3zg4b
发表时间：
1998
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Jeffrey S. Salowe;David M. Warme
通讯作者：
David M. Warme
图上斯坦纳问题的 11/6 近似算法
DOI：
10.1016/s0167-5060(08)70655-1
发表时间：
1992
期刊：
Annals of discrete mathematics
影响因子：
--
作者：
A. Zelikovsky
通讯作者：
A. Zelikovsky