Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree

DOI10.1145/3357713.3384301MaRDI QIDQ5144967zbMATH OpenOpenAlexFDO

Authors Jaroslaw Byrka, Fabrizio Grandoni, Afrouz Jabal Ameli

Publication date 19 January 2021

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

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

zbMATH Keywords

approximation algorithmsconnectivity augmentationSteiner tree

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
• On the Cycle Augmentation Problem: hardness and approximation algorithms
• On the cycle augmentation problem: hardness and approximation algorithms
• Better-than-\(\frac{4}{3}\)-approximations for leaf-to-leaf tree and connectivity augmentation
• Approximating connectivity augmentation problems

Cited in

(18)

• Approximation algorithms for vertex-connectivity augmentation on the cycle
• Approximation algorithms for connectivity augmentation problems
• 2-node-connectivity network design
• On the cycle augmentation problem: hardness and approximation algorithms
• Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
• Flexible Graph Connectivity
• Node connectivity augmentation via iterative randomized rounding
• Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
• Network augmentation for disaster‐resilience against geographically correlated failure
• A (1.5+)-approximation algorithm for weighted connectivity augmentation
• Better-than-\(\frac{4}{3}\)-approximations for leaf-to-leaf tree and connectivity augmentation
• Streaming algorithms for connectivity augmentation
• Better-than-2 approximations for weighted tree augmentation and applications to Steiner tree
• Hypergraph connectivity augmentation in strongly polynomial time
• Parameterized algorithms for node connectivity augmentation problems
• Bridging the gap between tree and connectivity augmentation: unified and stronger approaches
• Streaming algorithms for network design
• Approximation schemes for planar graph connectivity problems

This page was built for publication: Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree

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