Advertisement
Published in:
2014 | OriginalPaper | Chapter
Steiner Tree 1.39-Approximation in Practice
Authors : Stephan Beyer, Markus Chimani
Published in: Mathematical and Engineering Methods in Computer Science
Publisher: Springer International Publishing
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
We consider the currently strongest Steiner tree approximation algorithm that has recently been published by Goemans, Olver, Rothvoß and Zenklusen (2012). It first solves a hypergraphic LP relaxation and then applies matroid theory to obtain an integral solution. The cost of the resulting Steiner tree is at most
$$(1.39 + \varepsilon )$$
-times the cost of an optimal Steiner tree where
$$\varepsilon $$
tends to zero as some parameter
$$k$$
tends to infinity. However, the degree of the polynomial running time depends on this constant
$$k$$
, so only small
$$k$$
are tractable in practice.
The algorithm has, to our knowledge, not been implemented and evaluated in practice before. We investigate different implementation aspects and parameter choices of the algorithm and compare tuned variants to an exact LP-based algorithm as well as to fast and simple
$$2$$
-approximations.