Approximation Algorithms for Steiner Tree Problems Based on Universal Solution Frameworks
Approximation Algorithms for Steiner Tree Problems Based on Universal Solution Frameworks
复制标题
基于通用解框架的斯坦纳树问题逼近算法
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Piotr Wygocki
中科院分区：
文献类型：
--
作者：
Krzysztof Ciebiera;Piotr Godlewski;P. Sankowski;Piotr Wygocki
本文总结了我们在PAAL项目中对斯坦纳树问题的几个解的实现工作。该项目的主要重点是开发近似算法的通用实现以及通用解决方案框架。特别是，我们使用局部搜索框架实现了Zelikovsky 11/6近似，以及Byrka等人使用迭代舍入框架实现了1.39近似。实验将这两种算法与贪婪2逼近、精确但指数时间的Dreyfus-Wagner算法以及Uchoa和Werneck最先进的局部搜索技术给出的结果进行了比较。本文的结果是双重的。一方面，我们证明了高级算法概念可以在c++中设计和有效地使用。另一方面，我们表明上述算法具有良好的理论保证，在实践中给出了不错的结果，但不如最先进的启发式方法。
This paper summarizes the work on implementing few solutions for the Steiner Tree problem which we undertook in the PAAL project. The main focus of the project is the development of generic implementations of approximation algorithms together with universal solution frameworks. In particular, we have implemented Zelikovsky 11/6-approximation using local search framework, and 1.39-approximation by Byrka et al. using iterative rounding framework. These two algorithms are experimentally compared with greedy 2-approximation, with exact but exponential time Dreyfus-Wagner algorithm, as well as with results given by a state-of-the-art local search techniques by Uchoa and Werneck. The results of this paper are twofold. On one hand, we demonstrate that high level algorithmic concepts can be designed and efficiently used in C++. On the other hand, we show that the above algorithms with good theoretical guarantees, give decent results in practice, but are inferior to state-of-the-art heuristical approaches.