Advertisement
Published in:
2011 | OriginalPaper | Chapter
Contraction-Based Steiner Tree Approximations in Practice
Authors : Markus Chimani, Matthias Woste
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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) parameter
k
tends to infinity, while the running time is exponentially dependent on this very
k
.
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.