Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs

DOI10.1137/1.9781611974782.157MaRDI QIDQ4575906zbMATH OpenOpenAlexFDO

Authors David Adjiashvili

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.03791

Mathematics Subject Classification ID

Connectivity (05C40) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Abstract: The Weighted Tree Augmentation Problem (WTAP) is a fundamental well-studied problem in the field of network design. Given an undirected tree $G=(V,E)$, an additional set of edges $LsubseteqVimesV$ disjoint from $E$ called extit{links}, and a cost vector $cinmathbb{R}_{geq0}^L$, WTAP asks to find a minimum-cost set $FsubseteqL$ with the property that $(V,EcupF)$ is $2$-edge connected. The special case where $c_{e}ll=1$ for all $ellinL$ is called the Tree Augmentation Problem (TAP). Both problems are known to be NP-hard. For the class of bounded cost vectors, we present a first improved approximation algorithm for WTAP since more than three decades. Concretely, for any $Minmathbb{Z}_{geq1}$ and $epsilon>0,$ we present an LP based $(delta+epsilon)$-approximation for WTAP restricted to cost vectors $c$ in $[1,M{]}^L$ for $deltaapprox1.96417$. For the special case of TAP we improve this factor to $frac53+epsilon$. Our results rely on a new LP, that significantly differs from existing LPs achieving improved bounds for TAP. We round a fractional solution in two phases. The first phase uses the fractional solution to decompose the tree and its fractional solution into so-called $$-simple pairs losing only an $epsilon$-factor in the objective function. We then show how to use the additional constraints in our LP combined with the $$-simple structure to round a fractional solution in each part of the decomposition.

Recommendations

• Beating approximation factor two for weighted tree augmentation with bounded costs
• Tight bounds for online weighted tree augmentation
• Tight bounds for online weighted tree augmentation
• scientific article; zbMATH DE number 6850362
• Improved approximation for tree augmentation: saving by rewiring
• Breaching the 2-approximation barrier for the forest augmentation problem
• Approximating (unweighted) tree augmentation via lift-and-project. II
• On the integrality ratio for tree augmentation
• Approximate search strategies for weighted trees
• Brief announcement: Distributed approximation for tree augmentation

Cited in

(17)

• LP-relaxations for tree augmentation
• Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
• Fast distributed approximation for TAP and 2-edge-connectivity
• On small-depth tree augmentations
• Approximation algorithms for connectivity augmentation problems
• 2-node-connectivity network design
• The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
• On the tree augmentation problem
• Fast distributed approximation for TAP and 2-edge-connectivity
• scientific article; zbMATH DE number 6850362 (Why is no real title available?)
• Beating approximation factor two for weighted tree augmentation with bounded costs
• How to Secure Matchings Against Edge Failures
• Tight bounds for online weighted tree augmentation
• scientific article; zbMATH DE number 7205039 (Why is no real title available?)
• Improved approximation for tree augmentation: saving by rewiring
• A (1.5+)-approximation algorithm for weighted connectivity augmentation
• Tight bounds for online weighted tree augmentation

This page was built for publication: Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575906)