A (Slightly) Improved Approximation Algorithm for Metric TSP

Anna R. Karlin (), Nathan Klein () and Shayan Oveis Gharan ()
Additional contact information
Anna R. Karlin: Department of Computer Science, University of Washington, Seattle, Washington 98103
Nathan Klein: Department of Computer Science, University of Washington, Seattle, Washington 98103
Shayan Oveis Gharan: Department of Computer Science, University of Washington, Seattle, Washington 98103

Operations Research, 2024, vol. 72, issue 6, 2543-2594

Abstract: For some ϵ > 10 − 36 , we give a randomized 3 / 2 − ϵ approximation algorithm for metric TSP.

Keywords: Optimization; approximation algorithms; maximum entropy distributions; strongly Rayleigh distributions; random spanning trees; traveling salesperson problem (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2338 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:72:y:2024:i:6:p:2543-2594

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().