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.ESA.2017.61
URN: urn:nbn:de:0030-drops-78345
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7834/
Go to the corresponding LIPIcs Volume Portal

Nutov, Zeev

On the Tree Augmentation Problem

pdf-format:
LIPIcs-ESA-2017-61.pdf (0.5 MB)

Abstract

In the Tree Augmentation problem we are given a tree T=(V,F) and a set E of edges with positive integer costs {c_e:e in E}. The goal is to augment T by a minimum cost edge set J subseteq E such that T cup J is 2-edge-connected. We obtain the following results.

Recently, Adjiashvili [SODA 17] introduced a novel LP for the problem and used it to break the 2-approximation barrier for instances when the maximum cost M of an edge in E is bounded by a constant; his algorithm computes a 1.96418+epsilon approximate solution in time n^{{(M/epsilon^2)}^{O(1)}}. Using a simpler LP, we achieve ratio 12/7+epsilon in time ^{O(M/epsilon^2)}. This also gives ratio better than 2 for logarithmic costs, and not only for constant costs. In addition, we will show that (for arbitrary costs) the problem admits ratio 3/2 for trees of diameter <= 7.

One of the oldest open questions for the problem is whether for unit costs (when M=1) the standard LP-relaxation, so called Cut-LP, has integrality gap less than 2. We resolve this open question by proving that for unit costs the integrality gap of the Cut-LP is at most 28/15=2-2/15. In addition, we will suggest another natural LP-relaxation that is much simpler than the ones in previous work, and prove that it has integrality gap at most 7/4.

BibTeX - Entry

@InProceedings{nutov:LIPIcs:2017:7834,
  author =	{Zeev Nutov},
  title =	{{On the Tree Augmentation Problem}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{61:1--61:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7834},
  URN =		{urn:nbn:de:0030-drops-78345},
  doi =		{10.4230/LIPIcs.ESA.2017.61},
  annote =	{Keywords: Tree augmentation, Logarithmic costs, Approximation algorithm, Half-integral extreme points, Integrality gap}
}

Keywords: Tree augmentation, Logarithmic costs, Approximation algorithm, Half-integral extreme points, Integrality gap
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

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