The traveling salesman problem on cubic and subcubic graphs

• 成果类型: Article
• 署名作者: Boyd, Sylvia; Sitters, Ren; van der Ster, Suzanne; Stougie, Leen
• 署名单位: University of Ottawa; Vrije Universiteit Amsterdam; Centrum Wiskunde & Informatica (CWI)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0620-1
• 发表日期: 2014
• 页码: 227-245
• 关键词: tsp; matchings

摘要

We study the traveling salesman problem (TSP) on the metric completion of cubic and subcubic graphs, which is known to be NP-hard. The problem is of interest because of its relation to the famous 4/3-conjecture for metric TSP, which says that the integrality gap, i.e., the worst case ratio between the optimal value of a TSP instance and that of its linear programming relaxation (the subtour elimination relaxation), is 4/3. We present the first algorithm for cubic graphs with approximation ratio 4/3. The proof uses polyhedral techniques in a surprising way, which is of independent interest. In fact we prove constructively that for any cubic graph on vertices a tour of length exists, which also implies the 4/3-conjecture, as an upper bound, for this class of graph-TSP. Recently, Momke and Svensson presented an algorithm that gives a 1.461-approximation for graph-TSP on general graphs and as a side result a 4/3-approximation algorithm for this problem on subcubic graphs, also settling the 4/3-conjecture for this class of graph-TSP. The algorithm by Momke and Svensson is initially randomized but the authors remark that derandomization is trivial. We will present a different way to derandomize their algorithm which leads to a faster running time. All of the latter also works for multigraphs.