Byrka, Jaroslaw and Grandoni, Fabrizio and Rothvoß, Thomas and Sanità, Laura (2013) Steiner Tree Approximation via Iterative Randomized Rounding. Journal of the ACM, 60 (1). p. 6. ISSN 0004-5411
Full text not available from this repository.Abstract
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, 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.
Item Type: | Scientific journal article, Newspaper article or Magazine article |
---|---|
Subjects: | Computer sciences |
Department/unit: | Dipartimento tecnologie innovative > Istituto Dalle Molle di studi sull’intelligenza artificiale USI-SUPSI |
Depositing User: | Fabrizio Grandoni |
Date Deposited: | 14 Mar 2014 08:18 |
Last Modified: | 23 May 2016 14:15 |
URI: | http://repository.supsi.ch/id/eprint/4472 |
Actions (login required)
View Item |