A Better-Than-2 Approximation for Weighted Tree Augmentation

Vera Traub; Rico Zenklusen

doi:10.1109/focs52979.2021.00010

FOCS2021顶会

A Better-Than-2 Approximation for Weighted Tree Augmentation

Vera Traub, Rico Zenklusen

arXiv DOI 出版方

2021年份

20被引次数

12顶会引用

摘要

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. −