A Better-Than-2 Approximation for Weighted Tree Augmentation

Vera Traub; Rico Zenklusen

doi:10.1109/focs52979.2021.00010

FOCS2021Top-tier venue

A Better-Than-2 Approximation for Weighted Tree Augmentation

Vera Traub, Rico Zenklusen

arXiv DOI Publisher

2021Year

20Citations

12Top-tier citations

Abstract

We present an approximation algorithm for Weighted Tree Augmentation with approximation factor 1 + $\ln 2+\varepsilon < 1.7$ . This is the first algorithm beating the longstanding factor of 2, which can be achieved through many standard techniques. −