Nutov, Zeev
On the Tree Augmentation Problem
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 2edgeconnected. We obtain the following results.
Recently, Adjiashvili [SODA 17] introduced a novel LP for the problem and used it to break the 2approximation 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 LPrelaxation, so called CutLP, has integrality gap less than 2. We resolve this open question by proving that for unit costs the integrality gap of the CutLP is at most 28/15=22/15. In addition, we will suggest another natural LPrelaxation 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:161:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770491},
ISSN = {18688969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7834},
URN = {urn:nbn:de:0030drops78345},
doi = {10.4230/LIPIcs.ESA.2017.61},
annote = {Keywords: Tree augmentation, Logarithmic costs, Approximation algorithm, Halfintegral extreme points, Integrality gap}
}
01.09.2017
Keywords: 

Tree augmentation, Logarithmic costs, Approximation algorithm, Halfintegral extreme points, Integrality gap 
Seminar: 

25th Annual European Symposium on Algorithms (ESA 2017)

Issue date: 

2017 
Date of publication: 

01.09.2017 