Strong Steiner Tree Approximations in Practice
Stephan Beyer, Markus Chimani · ACM Journal of Experimental Algorithmics · 2019
In this experimental study, we consider Steiner tree approximation algorithms that guarantee a constant approximation ratio smaller than 2. The considered greedy algorithms and approaches based on linear programming involve the incorporation of k -restricted full components for some k ≥ 3. For most of the algorithms, their strongest theoretical approximation bounds are only achieved for k → ∞. However, the running time is also exponentially dependent on k , so only small k are tractable in practice. We investigate different implementation aspects and parameter choices that finally allow us to construct algorithms (somewhat) feasible for practical use. We compare the algorithms against each other, to an exact algorithm based on integer linear programs, and to fast and simple 2-approximations as well as state-of-the-art heuristics.