On small-depth tree augmentations Article Swipe
Related Concepts
Tree (set theory)
Mathematical proof
Constructive
Mathematics
Matching (statistics)
Linear programming relaxation
Relaxation (psychology)
Combinatorics
Approximation algorithm
Discrete mathematics
Algorithm
Computer science
Linear programming
Statistics
Geometry
Medicine
Operating system
Process (computing)
Internal medicine
Ojas Parekh
,
R. Ravi
,
Michael Zlatin
·
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.1016/j.orl.2022.10.002
· OA: W3208440388
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.1016/j.orl.2022.10.002
· OA: W3208440388
We study the Weighted Tree Augmentation Problem for general link costs. We show that the integrality gap of the odd-LP relaxation for the (weighted) Tree Augmentation Problem for a k-level tree instance is at most 2−12k−1. For 2- and 3-level trees, these ratios are 32 and 74 respectively. Our proofs are constructive and yield polynomial-time approximation algorithms with matching guarantees.
Related Topics
Finding more related topics…