Get 20M+ Full-Text Papers For Less Than $1.50/day. Subscribe now for You or Your Team.

Learn More →

An improved LP-based approximation for steiner tree

An improved LP-based approximation for steiner tree An Improved LP-based Approximation for Steiner Tree — Institute of Mathematics, EPFL Lausanne, Switzerland Jarosław Byrka jaroslaw.byrka@ep ‚.ch Thomas Rothvoß grandoni@disp.uniroma2.it Institute of Mathematics, EPFL Lausanne, Switzerland University of Tor Vergata Rome, Italy Fabrizio Grandoni ¡ Institute of Mathematics, EPFL Lausanne, Switzerland Laura Sanità § thomas.rothvoss@ep ‚.ch laura.sanita@ep ‚.ch 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, nd a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from 2 to the current best 1.55 [Robins,Zelikovsky-SIDMA ™05]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP-relaxation for Steiner tree with integrality gap smaller than 2 [Vazirani,RajagopalanSODA ™99]. In this paper we improve the approximation factor for Steiner tree, developing an LP-based approximation algorithm. Our algorithm is based on a, seemingly novel, iterative randomized rounding technique. We consider a directedcomponent cut relaxation for the k-restricted Steiner tree problem. We sample one of these components with probability proportional to the value of the associated variable in the optimal fractional solution and contract it. We iterate this process for http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

An improved LP-based approximation for steiner tree

Association for Computing Machinery — Jun 5, 2010

Loading next page...
/lp/association-for-computing-machinery/an-improved-lp-based-approximation-for-steiner-tree-VXcVZ7Rpme

References (50)

Datasource
Association for Computing Machinery
Copyright
Copyright © 2010 by ACM Inc.
ISBN
978-1-4503-0050-6
doi
10.1145/1806689.1806769
Publisher site
See Article on Publisher Site

Abstract

An Improved LP-based Approximation for Steiner Tree — Institute of Mathematics, EPFL Lausanne, Switzerland Jarosław Byrka jaroslaw.byrka@ep ‚.ch Thomas Rothvoß grandoni@disp.uniroma2.it Institute of Mathematics, EPFL Lausanne, Switzerland University of Tor Vergata Rome, Italy Fabrizio Grandoni ¡ Institute of Mathematics, EPFL Lausanne, Switzerland Laura Sanità § thomas.rothvoss@ep ‚.ch laura.sanita@ep ‚.ch 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, nd a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from 2 to the current best 1.55 [Robins,Zelikovsky-SIDMA ™05]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP-relaxation for Steiner tree with integrality gap smaller than 2 [Vazirani,RajagopalanSODA ™99]. In this paper we improve the approximation factor for Steiner tree, developing an LP-based approximation algorithm. Our algorithm is based on a, seemingly novel, iterative randomized rounding technique. We consider a directedcomponent cut relaxation for the k-restricted Steiner tree problem. We sample one of these components with probability proportional to the value of the associated variable in the optimal fractional solution and contract it. We iterate this process for

There are no references for this article.