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

DOI10.1145/3357713.3384301OpenAlexW3035043943MaRDI QIDQ5144967

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 algorithmsSteiner treeconnectivity augmentation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (9)

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 ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ On the cycle augmentation problem: hardness and approximation algorithms ⋮ Approximation algorithms for vertex-connectivity augmentation on the cycle ⋮ Approximation algorithms for connectivity augmentation problems ⋮ 2-node-connectivity network design

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