arXiv Open Access 2026

Better approximation guarantee for Asymmetric TSP

Jens Vygen

Lihat Sumber

Abstrak

We improve the approximation ratio for the Asymmetric TSP to less than 15. We also obtain improved ratios for the special case of unweighted digraphs and the generalization where we ask for a minimum-cost tour with given (distinct) endpoints. Moreover, we prove better upper bounds on the integrality ratios of the natural LP relaxations.

Topik & Kata Kunci

cs.DS math.CO

Penulis (1)

Jens Vygen

Format Sitasi

APA MLA BibTeX

Vygen, J. (2026). Better approximation guarantee for Asymmetric TSP. https://arxiv.org/abs/2603.14334

Akses Cepat

Lihat di Sumber

Informasi Jurnal

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