arXiv Open Access 2021

A Better-Than-2 Approximation for Weighted Tree Augmentation

Vera Traub Rico Zenklusen

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.DS math.OC

Penulis (2)

Vera Traub

Rico Zenklusen

Format Sitasi

APA MLA BibTeX

Traub, V., Zenklusen, R. (2021). A Better-Than-2 Approximation for Weighted Tree Augmentation. https://arxiv.org/abs/2104.07114

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2021
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓