Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Steiner Tree Approximation via Iterative Randomized Rounding
 
research article

Steiner Tree Approximation via Iterative Randomized Rounding

Byrka, Jaroslaw
•
Grandoni, Fabrizio
•
Rothvoss, Thomas  
Show more
2013
Journal of the ACM

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, \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.

  • Files
  • Details
  • Metrics
Type
research article
DOI
10.1145/2432622.2432628
Web of Science ID

WOS:000315799200006

Author(s)
Byrka, Jaroslaw
Grandoni, Fabrizio
Rothvoss, Thomas  
Sanità, Laura  
Date Issued

2013

Publisher

Assoc Computing Machinery

Published in
Journal of the ACM
Volume

60

Issue

1

Start page

6

Subjects

approximation algorithms

•

linear programming relxations

•

network design

•

randomized algorithms

Note

Invited publication

Editorial or Peer reviewed

NON-REVIEWED

Written at

EPFL

EPFL units
DISOPT  
Available on Infoscience
November 21, 2010
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/57997
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés