Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Steiner Tree 1.39-Approximation in Practice
verfasst von : Stephan Beyer, Markus Chimani
Erschienen in: Mathematical and Engineering Methods in Computer Science
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.