On small-depth tree augmentations

DOI10.1016/J.ORL.2022.10.002MaRDI QIDQ2102832zbMATH OpenOpenAlexFDO

Authors Ojas Parekh, R. Ravi, Michael Zlatin

Publication date 12 December 2022

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

approximation algorithmintegrality gapnetwork design

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Recommendations

• On the tree augmentation problem
• LP-relaxations for tree augmentation
• scientific article; zbMATH DE number 7205039
• Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
• On the integrality ratio for tree augmentation

Cites work

• scientific article; zbMATH DE number 6850362 (Why is no real title available?)
• scientific article; zbMATH DE number 1405806 (Why is no real title available?)
• A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
• A bidirected generalization of network matrices
• A simplified \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
• Approximation Algorithms for Graph Augmentation
• Approximation Algorithms for Several Graph Augmentation Problems
• Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
• Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• Improved approximation for tree augmentation: saving by rewiring
• On the integrality ratio for tree augmentation
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• Optimization with binet matrices
• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts

Cited in

(1)

• LP-relaxations for tree augmentation

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

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