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.2016.13
URN: urn:nbn:de:0030-drops-66366
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6636/
Go to the corresponding LIPIcs Volume Portal

Kortsarz, Guy ; Nutov, Zeev

LP-Relaxations for Tree Augmentation

pdf-format:
LIPIcs-APPROX-RANDOM-2016-13.pdf (1 MB)

Abstract

In the Tree Augmentation Problem (TAP) the goal is to augment a tree T by a minimum size edge set F from a given edge set E such that T+F is 2-edge-connected. The best approximation ratio known for TAP is 1.5. In the more general Weighted TAP problem, F should be of minimum weight. Weighted TAP admits several 2-approximation algorithms w.r.t. the standard cut-LP relaxation. The problem is equivalent to the problem of covering a laminar set family. Laminar set families play an important role in the design of approximation algorithms for connectivity network design problems. In fact, Weighted TAP is the simplest connectivity network design problem for which a ratio better than 2 is not known. Improving this "natural" ratio is a major open problem, which may have implications on many other network design problems. It seems that achieving this goal requires finding an LP-relaxation with integrality gap better than 2, which is an old open problem even for TAP. In this paper we introduce two different LP-relaxations, and for each of them give a simple algorithm that computes a feasible solution for TAP of size at most 7/4 times the optimal LP value. This gives some hope to break the ratio 2 for the weighted case.

BibTeX - Entry

@InProceedings{kortsarz_et_al:LIPIcs:2016:6636,
  author =	{Guy Kortsarz and Zeev Nutov},
  title =	{{LP-Relaxations for Tree Augmentation}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6636},
  URN =		{urn:nbn:de:0030-drops-66366},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.13},
  annote =	{Keywords: Tree Augmentation; LP-relaxation; Laminar family; Approximation algorithms}
}

Keywords: Tree Augmentation; LP-relaxation; Laminar family; Approximation algorithms
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Issue Date: 2016
Date of publication: 06.09.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI