Better approximation guarantee for Asymmetric TSP
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918389520269312 |
|---|---|
| author | Vygen, Jens |
| author_facet | Vygen, Jens |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_14334 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Better approximation guarantee for Asymmetric TSP Vygen, Jens Data Structures and Algorithms Combinatorics 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. |
| title | Better approximation guarantee for Asymmetric TSP |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2603.14334 |