Local Search for Weighted Tree Augmentation and Steiner Tree

We present a technique that allows for improving on some relative greedy procedures by well-chosen (non-oblivious) local search algorithms. Relative greedy procedures are a particular type of greedy algorithm that start with a simple, though weak, solution, and iteratively replace parts of this starting solution by stronger components. Some well-known applications of relative greedy algorithms include approximation algorithms for Steiner Tree and, more recently, for connectivity augmentation problems. The main application of our technique leads to a (1.5 + ∊)-approximation for Weighted Tree Augmentation, improving on a recent relative greedy based method with approximation factor 1 + ln 2 + ∊ ≈ 1.69. Furthermore, we show how our local search technique can be applied to Steiner Tree, leading to an alternative way to obtain the currently best known approximation factor of ln 4 + ∊. Contrary to prior methods, our approach is purely combinatorial without the need to solve an LP. Nevertheless, the solution value can still be bounded in terms of the well-known hypergraphic LP, leading to an alternative, and arguably simpler, technique to bound its integrality gap by ln 4.