×

Contraction-based Steiner tree approximations in practice. (English) Zbl 1329.68286

Asano, Takao (ed.) et al., Algorithms and computation. 22nd international symposium, ISAAC 2011, Yokohama, Japan, December 5–8, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-25590-8/pbk). Lecture Notes in Computer Science 7074, 40-49 (2011).
Summary: 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.
For the entire collection see [Zbl 1228.68006].

MSC:

68W25 Approximation algorithms
05C22 Signed and weighted graphs
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI