Better-Than-2 Approximations for Weighted Tree Augmentation and Applications to Steiner Tree
OPEN ACCESS
Author / Producer
Date
2025-04
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
We present the first approximation algorithms for the Weighted Tree Augmentation Problem (WTAP) that beat the longstanding approximation factor of 2, which can be achieved through standard techniques. The core of our approach is a novel decomposition theorem based on a well-chosen class of thin components. The decomposition theorem asserts that for any pair of a highly structured (but potentially expensive) WTAP solution and a cheaper WTAP solution, there is a way to decompose the cheaper solution into thin components, one of which allows for improving the structured solution. Together with the fact that we can efficiently optimize over thin components through a dynamic program, our decomposition theorem leads to a relative greedy algorithm for WTAP that is a (1 + ln 2 + ϵ)-approximation.Moreover, we present an approach to improve on some relative greedy procedures by well-chosen (non-oblivious) local search algorithms. The main application of this approach leads to a (1.5 + $\epsilon$)-approximation for WTAP. Furthermore, for the Steiner Tree Problem, it provides 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, way to bound its integrality gap by ln 4.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
72 (2)
Pages / Article No.
16
Publisher
Association for Computing Machinery
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Weighted tree augmentation; Steiner Trees; approximation algorithms; combinatorial optimization
Organisational unit
09487 - Zenklusen, Rico / Zenklusen, Rico
Notes
Funding
184622 - Toward Stronger Approximation Algorithms for Fundamental Network Design and Optimization Problems (SNF)
817750 - Fundamental Problems at the Interface of Combinatorial Optimization with Integer Programming and Online Optimization (EC)
817750 - Fundamental Problems at the Interface of Combinatorial Optimization with Integer Programming and Online Optimization (EC)