Steiner tree 1.39-approximation in practice

Autor(en): Beyer, S.
Chimani, M. 
Herausgeber: Dvorak, Z.
Kofron, J.
Hlineny, P.
Matula, P.
Pala, K.
Jaros, J.
Korenek, J.
Stichwörter: Algorithms; Approximation algorithms; Matrix algebra, Implementation aspects; Integral solutions; LP relaxation; Matroid theory; Parameter choice; Running time; Steiner trees, Trees (mathematics)
Erscheinungsdatum: 2014
Herausgeber: Springer Verlag
Journal: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen: 8934
Startseite: 60
Seitenende: 72
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 ε)-times the cost of an optimal Steiner tree where ε 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. © Springer International Publishing Switzerland 2014.
Conference of 9th International Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, MEMICS 2014 ; Conference Date: 17 October 2014 Through 19 October 2014; Conference Code:112649
ISBN: 9783319148953
ISSN: 03029743
DOI: 10.1007/978-3-319-14896-0_6
Externe URL:

Show full item record

Page view(s)

Last Week
Last month
checked on Apr 18, 2024

Google ScholarTM