An improved LP-based approximation for steiner tree

By Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoss, Laura Sanità. Symposium on the Theory of Computing, 2010

323 citations recorded by the source corpus.

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 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,Rajagopalan-SODA'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 directed-component 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 a proper number of times and finally output the sampled components together with a minimum-cost terminal spanning tree in the remaining graph. Our algorithm delivers a solution of cost at most ln(4) times the cost of an optimal k-restricted Steiner tree. This directly implies a ln(4)+ε<1.39 approximation for Steiner tree. 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.

Subfields: Computational Theory and Mathematics, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/9b55c034bec59410a3129780827b481354c99b08

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

  1. David B. Shmoys
  2. David P. Williamson
  3. Sariel Har-Peled
  4. Yaron Shaposhnik
  5. A. Kukanov
  6. Rama Cont
  7. Cynthia Rudin

In Electrical and Electronic Engineering

  1. David B. Shmoys
  2. David P. Williamson

Citations in the corpus