License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.176
URN: urn:nbn:de:0030-drops-46962
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4696/
Feldmann, Andreas Emil ;
Könemann, Jochen ;
Olver, Neil ;
Sanità, Laura
On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree
Abstract
The bottleneck of the currently best (ln(4) + epsilon)-approximation algorithm for the NP-hard Steiner tree problem is the solution of its large, so called hypergraphic, linear programming relaxation (HYP). Hypergraphic LPs are NP-hard to solve exactly, and it is a formidable computational task to even approximate them sufficiently well.
We focus on another well-studied but poorly understood LP relaxation of the problem: the bidirected cut relaxation (BCR). This LP is compact, and can therefore be solved efficiently. Its integrality gap is known to be greater than 1.16, and while this is widely conjectured to be close to the real answer, only a (trivial) upper bound of 2 is known.
In this paper, we give an efficient constructive proof that BCR and HYP are polyhedrally equivalent in instances that do not have an (edge-induced) claw on Steiner vertices, i.e., they do not contain a Steiner vertex with 3 Steiner neighbors. This implies faster ln(4)-approximations for these graphs, and is a significant step forward from the previously known equivalence for (so called quasi-bipartite) instances in which Steiner vertices form an independent set. We complement our results by showing that even restricting to instances where Steiner vertices induce one single star, determining whether the two relaxations are equivalent is NP-hard.
BibTeX - Entry
@InProceedings{feldmann_et_al:LIPIcs:2014:4696,
author = {Andreas Emil Feldmann and Jochen K{\"o}nemann and Neil Olver and Laura Sanit{\`a}},
title = {{On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
pages = {176--191},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-74-3},
ISSN = {1868-8969},
year = {2014},
volume = {28},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4696},
URN = {urn:nbn:de:0030-drops-46962},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.176},
annote = {Keywords: Steiner tree, bidirected cut relaxation, hypergraphic relaxation, polyhedral equivalence, approximation algorithms}
}
|
Keywords: |
|
Steiner tree, bidirected cut relaxation, hypergraphic relaxation, polyhedral equivalence, approximation algorithms |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) |
|
Issue Date: |
|
2014 |
|
Date of publication: |
|
04.09.2014 |
