A (Slightly) Improved Approximation Algorithm for Metric TSP

• 成果类型: Article
• 署名作者: Karlin, Anna R.; Klein, Nathan; Gharan, Shayan Oveis
• 署名单位: University of Washington; University of Washington Seattle
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2338
• 发表日期: 2024
• 页码: 2543-2594
• 关键词: traveling-salesman problem; bounds

摘要

For some epsilon > 10(-36), we give a randomized 3/2 - epsilon approximation algorithm for metric TSP.