000155204 001__ 155204
000155204 005__ 20190316234939.0
000155204 0247_ $$2doi$$a10.1145/2432622.2432628
000155204 02470 $$2ISI$$a000315799200006
000155204 037__ $$aARTICLE
000155204 245__ $$aSteiner Tree Approximation via Iterative Randomized Rounding
000155204 269__ $$a2013
000155204 260__ $$bAssoc Computing Machinery$$c2013$$aNew York
000155204 300__ $$a33
000155204 336__ $$aJournal Articles
000155204 500__ $$aInvited publication
000155204 520__ $$aThe 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.
000155204 6531_ $$aapproximation algorithms
000155204 6531_ $$alinear programming relxations
000155204 6531_ $$anetwork design
000155204 6531_ $$arandomized algorithms
000155204 700__ $$aByrka, Jaroslaw
000155204 700__ $$aGrandoni, Fabrizio
000155204 700__ $$0243826$$g183730$$aRothvoss, Thomas
000155204 700__ $$aSanità, Laura$$g190471$$0243827
000155204 773__ $$j60$$tJournal of the ACM$$k1$$q6
000155204 8564_ $$uhttps://infoscience.epfl.ch/record/155204/files/steinertree-journalV11.pdf$$zn/a$$s461244$$yn/a
000155204 909C0 $$xU11879$$0252111$$pDISOPT
000155204 909CO $$qGLOBAL_SET$$pSB$$ooai:infoscience.tind.io:155204$$particle
000155204 917Z8 $$x183730
000155204 917Z8 $$x183730
000155204 917Z8 $$x148230
000155204 937__ $$aEPFL-ARTICLE-155204
000155204 973__ $$rNON-REVIEWED$$sPUBLISHED$$aEPFL
000155204 980__ $$aARTICLE