Improved approximation for tree augmentation: saving by rewiring

DOI10.1145/3188745.3188898MaRDI QIDQ5230326zbMATH OpenOpenAlexFDO

Authors Fabrizio Grandoni, Christos Kalaitzis, Rico Zenklusen

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial optimizationapproximation algorithmstree augmentation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Abstract: The Tree Augmentation Problem (TAP) is a fundamental network design problem in which we are given a tree and a set of additional edges, also called emph{links}. The task is to find a set of links, of minimum size, whose addition to the tree leads to a $2$-edge-connected graph. A long line of results on TAP culminated in the previously best known approximation guarantee of $1.5$ achieved by a combinatorial approach due to Kortsarz and Nutov [ACM Transactions on Algorithms 2016], and also by an SDP-based approach by Cheriyan and Gao [Algorithmica 2017]. Moreover, an elegant LP-based $(1.5+epsilon)$-approximation has also been found very recently by Fiorini, Gross, K"onemann, and Sanit'a [SODA 2018]. In this paper, we show that an approximation factor below $1.5$ can be achieved, by presenting a $1.458$-approximation that is based on several new techniques.

Recommendations

• LP-relaxations for tree augmentation
• scientific article; zbMATH DE number 6850362
• Beating approximation factor two for weighted tree augmentation with bounded costs
• Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
• LP-relaxations for tree augmentation

Cited in

(33)

• Beating approximation factor two for weighted tree augmentation with bounded costs
• Fast distributed approximation for TAP and 2-edge-connectivity
• Tight bounds for online weighted tree augmentation
• Covering a laminar family by leaf to leaf links
• Tight bounds for online weighted tree augmentation
• Better-than-2 approximations for weighted tree augmentation and applications to Steiner tree
• On the tree augmentation problem
• Approximation algorithms for vertex-connectivity augmentation on the cycle
• A technique for obtaining true approximations for \(k\)-center with covering constraints
• Flexible graph connectivity
• A technique for obtaining true approximations for k-center with covering constraints
• The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
• 2-node-connectivity network design
• Node connectivity augmentation via iterative randomized rounding
• An Improved Approximation Algorithm for the Matching Augmentation Problem
• Better-than-\(\frac{4}{3}\)-approximations for leaf-to-leaf tree and connectivity augmentation
• Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
• Approximation algorithms for connectivity augmentation problems
• scientific article; zbMATH DE number 6850362 (Why is no real title available?)
• Approximation algorithms for node and element connectivity augmentation problems
• A simple LP-based approximation algorithm for the matching augmentation problem
• Streaming algorithms for connectivity augmentation
• Flexible Graph Connectivity
• A (1.5+)-approximation algorithm for weighted connectivity augmentation
• A 4/3 approximation for 2-vertex-connectivity
• LP-relaxations for tree augmentation
• Approximating (unweighted) tree augmentation via lift-and-project. II
• LP-relaxations for tree augmentation
• 2-node-connectivity network design
• Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
• On the cycle augmentation problem: hardness and approximation algorithms
• Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
• On small-depth tree augmentations

This page was built for publication: Improved approximation for tree augmentation: saving by rewiring

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