On Small-Depth Tree Augmentations

Ojas Parekh, R. Ravi, Michael Zlatin

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…