Steiner Tree Approximation via Iterative Randomized Rounding
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 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].
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Feb 01, 2013
- Source ID
- 10.1145/2432622.2432628
Entities
People
- Fabrizio Grandoni
- Jarosław Byrka
- Laura Sanità
- Thomas Rothvoss
Organizations
- Alexander von Humboldt Foundation
- Division of Computing and Communication Foundations
- European Research Council
- Foundation for Polish Science
- Ministry of Science and Higher Education
- Office of Naval Research
- Swiss Federal Institute of Technology in Lausanne
- University of Waterloo
- University of Wrocław
- Università della Svizzera italiana