Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours

• 成果类型: Article
• 署名作者: Haddadan, Arash; Newman, Alantha
• 署名单位: Carnegie Mellon University; Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01784-w
• 发表日期: 2023
• 页码: 595-620
• 关键词: traveling salesman problem; tsp; graphs

摘要

We present a new approach for gluing tours over certain tight, 3-edge cuts. Gluing over 3-edge cuts has been used in algorithms for finding Hamilton cycles in special graph classes and in proving bounds for 2-edge-connected subgraph problem, but not much was known in this direction for gluing connected multigraphs. We apply this approach to the traveling salesman problem (TSP) in the case when the objective function of the subtour elimination relaxation is minimized by a theta-cyclic point: x(e) is an element of (0, theta, 1 - theta, 1), where the support graph is subcubic and each vertex is incident to at least one edge with x-value 1. Such points are sufficient to resolve TSP in general. For these points, we construct a convex combination of tours in which we can reduce the usage of edges with x-value 1 from the 3/2 of Christofides algorithm to 3/2 - theta/10 while keeping the usage of edges with fractional x-value the same as Christofides algorithm. A direct consequence of this result is for the Uniform Cover Problem for TSP: In the case when the objective function of the subtour elimination relaxation is minimized by a 2/3-uniform point: x(e) is an element of (0, 2/3), we give a 17/12-approximation algorithm for TSP. For such points, this lands us halfway between the approximation ratios 3/2 of Christofides algorithm and 4/3 implied by the famous four-thirds conjecture.