Improved approximations for cubic bipartite and cubic TSP

• 成果类型: Article
• 署名作者: van Zuylen, Anke
• 署名单位: William & Mary
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1211-y
• 发表日期: 2018
• 页码: 399-413
• 关键词: traveling-salesman problem; graphic tsp

摘要

We show improved approximation guarantees for the traveling salesman problem on cubic bipartite graphs and cubic graphs. For connected cubic bipartite graphs with n nodes, we improve on recent results of Karp and Ravi by giving a local improvement algorithm that finds a tour of length at most 5/ 4n -2. For 2-connected cubic graphs, we show that the techniques of Momke and Svensson can be combined with the techniques of Correa, Larre and Soto, to obtain a tour of length at most ('4/ 3 -1/ 8754)n.