155204
20190316234939.0
doi
10.1145/2432622.2432628
ISI
000315799200006
ARTICLE
Steiner Tree Approximation via Iterative Randomized Rounding
2013
New York
Assoc Computing Machinery
2013
33
Journal Articles
Invited publication
The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from 2 to 1.55 [Robins,Zelikovsky-'05]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP relaxation of Steiner tree with integrality gap smaller than 2 [Vazirani,Rajagopalan-'99]. In this paper we present an LP-based approximation algorithm for Steiner tree with an improved approximation factor. Our algorithm is based on a, seemingly novel, \emph{iterative randomized rounding} technique. We consider an LP relaxation of the problem, which is based on the notion of directed components. We sample one component with probability proportional to the value of the associated variable in a fractional solution: the sampled component is contracted and the LP is updated consequently. We iterate this process until all terminals are connected. Our algorithm delivers a solution of cost at most ln(4)+\eps<1.39 times the cost of an optimal Steiner tree. The algorithm can be derandomized using the method of limited independence. As a byproduct of our analysis, we show that the integrality gap of our LP is at most 1.55, hence answering to the mentioned open question. This might have consequences for a number of related problems.
approximation algorithms
linear programming relxations
network design
randomized algorithms
Byrka, Jaroslaw
Grandoni, Fabrizio
243826
Rothvoss, Thomas
183730
243827
SanitÃ , Laura
190471
60
1
6
Journal of the ACM
461244
http://infoscience.epfl.ch/record/155204/files/steinertree-journalV11.pdf
n/a
n/a
252111
DISOPT
U11879
oai:infoscience.tind.io:155204
SB
article
GLOBAL_SET
183730
183730
148230
EPFL-ARTICLE-155204
EPFL
NON-REVIEWED
PUBLISHED
ARTICLE