Contraction-Based Steiner Tree Approximations in Practice
Contraction-Based Steiner Tree Approximations in Practice
复制标题
实践中基于收缩的斯坦纳树近似
DOI：
10.1007/978-3-642-25591-5_6
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
M. Woste
中科院分区：
文献类型：
--
作者：
M. Chimani;M. Woste
在这个实验研究中，我们考虑基于收缩的Steiner树近似。这个类包含唯一的近似算法，保证一个恒定的近似比低于2，仍然可以在实践中应用。尽管它们在理论上有了生动的发展，但据我们所知，这些算法在实践中从未被彻底研究过，这是特别有趣的，因为大多数这些算法的近似保证只有在某些情况下才成立。（常数）参数k趋于无穷大，而运行时间是指数依赖于这个veryk。我们研究不同的实现方面和参数的选择，最终使我们能够构建算法实际使用可行。然后，我们将这些算法相互比较，并与最先进的方法进行比较。
In this experimental study we consider contraction-based Steiner tree approximations. This class contains the only approximation algorithms that guarantee a constant approximation ratio below 2 and still may be applicable in practice. Despite their vivid evolution in theory, these algorithms have, to our knowledge, never been thoroughly investigated in practice before, which is particularly interesting as most of these algorithms’ approximation guarantees only hold when some (constant) parameterktends to infinity, while the running time is exponentially dependent on this veryk.We investigate different implementation aspects and parameter choices which finally allow us to construct algorithms feasible for practical use. Then we compare these algorithms against each other and against state-of-the-art approaches.
登录
查看更多内容
大型斯坦纳问题精确解的双重启发式
DOI：
--
发表时间：
2001
期刊：
Electron. Notes Discret. Math.
影响因子：
--
作者：
M. P. D. Aragão;Eduardo Uchoa;Renato F. Werneck
通讯作者：
Renato F. Werneck
图中斯坦纳问题的混合局部搜索
DOI：
--
发表时间：
2001
期刊：
影响因子：
--
作者：
M. P. D. Aragão;C. Ribeiro;Eduardo Uchoa;Renato F. Werneck
通讯作者：
Renato F. Werneck
LATIN 2000：理论信息学：第四届拉丁美洲研讨会，乌拉圭埃斯特角城，2000 年 4 月 10 日至 14 日会议记录
DOI：
--
发表时间：
2000
期刊：
Lecture Notes in Computer Science
影响因子：
--
作者：
G. Gonnet;D. Panario;Alfredo Viola
通讯作者：
Alfredo Viola
网络中斯坦纳问题的算法
DOI：
--
发表时间：
2003
期刊：
影响因子：
--
作者：
Tobias Polzin
通讯作者：
Tobias Polzin
DOI：
--
发表时间：
2002
期刊：
Lecture Notes in Computer Science
影响因子：
--
作者：
D. Mount;C. Stein
通讯作者：
C. Stein