Bridging the gap between tree and connectivity augmentation: unified and stronger approaches

DOI10.1145/3406325.3451086arXiv2012.00086OpenAlexW3166580633MaRDI QIDQ6087009

Vera Traub, Rico Zenklusen, Unnamed Author

Publication date: 14 November 2023

Published in: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial optimizationapproximation algorithmsconnectivity augmentation problemtree augmentation problemcacti augmentation problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (9)

An Improved Approximation Algorithm for the Matching Augmentation Problem ⋮ A simple LP-based approximation algorithm for the matching augmentation problem ⋮ Node connectivity augmentation via iterative randomized rounding ⋮ Complexity of (arc)-connectivity problems involving arc-reversals or deorientations ⋮ Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ 2-node-connectivity network design ⋮ Approximation algorithms for vertex-connectivity augmentation on the cycle ⋮ Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem

This page was built for publication: Bridging the gap between tree and connectivity augmentation: unified and stronger approaches