Steiner tree 1.39-approximation in practice

DC FieldValueLanguage
dc.contributor.authorBeyer, S.
dc.contributor.authorChimani, M.
dc.contributor.editorDvorak, Z.
dc.contributor.editorKofron, J.
dc.contributor.editorHlineny, P.
dc.contributor.editorMatula, P.
dc.contributor.editorPala, K.
dc.contributor.editorJaros, J.
dc.contributor.editorKorenek, J.
dc.date.accessioned2021-12-23T16:32:50Z-
dc.date.available2021-12-23T16:32:50Z-
dc.date.issued2014
dc.identifier.isbn9783319148953
dc.identifier.issn03029743
dc.identifier.urihttps://osnascholar.ub.uni-osnabrueck.de/handle/unios/17543-
dc.descriptionConference 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
dc.description.abstractWe 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.
dc.description.sponsorshipDeutsche ForschungsgemeinschaftDeutsche Forschungsgemeinschaft,DFG,CH 897/1-1; Funded by the German Research Foundation (DFG), project CH 897/1-1.; Honeywell; redhat; YSOFT
dc.language.isoen
dc.publisherSpringer Verlag
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.subjectAlgorithms
dc.subjectApproximation algorithms
dc.subjectMatrix algebra, Implementation aspects
dc.subjectIntegral solutions
dc.subjectLP relaxation
dc.subjectMatroid theory
dc.subjectParameter choice
dc.subjectRunning time
dc.subjectSteiner trees, Trees (mathematics)
dc.titleSteiner tree 1.39-approximation in practice
dc.typeconference paper
dc.identifier.doi10.1007/978-3-319-14896-0_6
dc.identifier.scopus2-s2.0-84927918115
dc.identifier.urlhttps://www.scopus.com/inward/record.uri?eid=2-s2.0-84927918115&doi=10.1007%2f978-3-319-14896-0_6&partnerID=40&md5=681026cd04e519eb9c6db817d3a9f926
dc.description.volume8934
dc.description.startpage60
dc.description.endpage72
dcterms.isPartOf.abbreviationLect. Notes Comput. Sci.
crisitem.author.orcid0000-0002-4681-5550-
crisitem.author.netidChMa572-
Show simple item record

Page view(s)

5
Last Week
1
Last month
0
checked on May 20, 2024

Google ScholarTM

Check

Altmetric