On Small-Depth Tree Augmentations

10/30/2021
by   Ojas Parekh, et al.
0

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 - 1/2^k-1. For 2- and 3-level trees, these ratios are 3/2 and 7/4 respectively. Our proofs are constructive and yield polynomial-time approximation algorithms with matching guarantees.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset