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