Improved approximation for tree augmentation: saving by rewiring
From MaRDI portal
Publication:5230326
DOI10.1145/3188745.3188898zbMath1429.68190arXiv1804.02242OpenAlexW2963193695MaRDI QIDQ5230326
Christos Kalaitzis, Rico Zenklusen, Fabrizio Grandoni
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
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items
An Improved Approximation Algorithm for the Matching Augmentation Problem, Flexible Graph Connectivity, A Technique for Obtaining True Approximations for k-Center with Covering Constraints, Tight bounds for online weighted tree augmentation, A simple LP-based approximation algorithm for the matching augmentation problem, On the tree augmentation problem, Node connectivity augmentation via iterative randomized rounding, The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm, Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree, On the cycle augmentation problem: hardness and approximation algorithms, Fast distributed approximation for TAP and 2-edge-connectivity, 2-node-connectivity network design, Tight Bounds for Online Weighted Tree Augmentation, Approximation algorithms for vertex-connectivity augmentation on the cycle, On small-depth tree augmentations, Approximation algorithms for connectivity augmentation problems, 2-node-connectivity network design, A technique for obtaining true approximations for \(k\)-center with covering constraints, Flexible graph connectivity
