2026-07-22T00:01:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7834 2024-03-06T10:41:23Z ddc:004 open_access

On the Tree Augmentation Problem Nutov, Zeev Tree augmentation Logarithmic costs Approximation algorithm Half-integral extreme points Integrality gap 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zeev Nutov 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.61 urn:nbn:de:0030-drops-78345 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.61 eng https://creativecommons.org/licenses/by/3.0/legalcode