On small-depth tree augmentations

DOI10.1016/j.orl.2022.10.002OpenAlexW3208440388MaRDI QIDQ2102832

R. Ravi, Ojas Parekh, Michael Zlatin

Publication date: 12 December 2022

Published in: Operations Research Letters (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmnetwork designintegrality gap

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
• On the integrality ratio for tree augmentation
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
• Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
• Optimization with binet matrices
• Approximation Algorithms for Several Graph Augmentation Problems
• Approximation Algorithms for Graph Augmentation
• Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2
• Improved approximation for tree augmentation: saving by rewiring
• A bidirected generalization of network matrices

This page was built for publication: On small-depth tree augmentations