### Steiner Tree Approximation via Iterative Randomized RoundingSteiner Tree Approximation via Iterative Randomized Rounding

Access Restriction
Subscribed

 Author Byrka, Jarosaw ♦ Grandoni, Fabrizio ♦ Rothvoss, Thomas ♦ Sanit, Laura Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2013 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Approximation algorithms ♦ Linear programming relaxations ♦ Network design ♦ Randomized algorithms Abstract The Steiner tree problem is one of the most fundamental $\textbf{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 and Zelikovsky 2005]. 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 [Rajagopalan and Vazirani 1999]. In this article we present an LP-based approximation algorithm for Steiner tree with an improved approximation factor. Our algorithm is based on a, seemingly novel, 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) + $\textit{ϵ}$ < 1.39 times the cost of an optimal Steiner tree. The algorithm can be derandomized using the method of limited independence. As a by-product of our analysis, we show that the integrality gap of our LP is at most 1.55, hence answering the mentioned open question. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2013-02-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 60 Issue Number 1 Page Count 33 Starting Page 1 Ending Page 33

#### Open content in new tab

Source: ACM Digital Library