On small-depth tree augmentations

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.