Can I read Strong Steiner Tree Approximations in Practice on EtoBox?

Strong Steiner Tree Approximations in Practice by Beyer, Stephan; Chimani, Markus is a scholarly article available to read on EtoBox.

What is Strong Steiner Tree Approximations in Practice about?

In this experimental study we consider Steiner tree approximations that guarantee a constant approximation of 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 \geq 3$. For most of the algorithms, their strongest theoretical approximation bounds are only achieved for $k \to \infty$. 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 LP-based algorithm, and to fast and simple $2$-approximations.

Author

Beyer, Stephan; Chimani, Markus

Published

2014

Language

EN