The salesman's improved tours for fundamental classes

• 成果类型: Article
• 署名作者: Boyd, Sylvia; Sebo, Andras
• 署名单位: University of Ottawa; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01455-3
• 发表日期: 2021
• 页码: 289-307
• 关键词: tsp

摘要

Finding the exact integrality gap a for the LP relaxation of the metric travelling salesman problem (TSP) has been an open problem for over 30 years, with little progress made. It is known that 4/3 = alpha = 3/2, and a famous conjecture states alpha = 4/3. It has also been conjectured that the integrality gap is achieved for half-integer basic solutions of the linear program. For this problem, essentially two fundamental classes of instances have been proposed. This fundamental property means that in order to show that the integrality gap is at most rho for all instances of the metric TSP, it is sufficient to show it only for the instances in the fundamental class. However, despite the importance and the simplicity of such classes, no apparent effort has been deployed for improving the integrality gap bounds for them. In this paper we take a natural first step in this endeavour, and consider the 1/2-integer points of one such class. We successfully improve the upper bound for the integrality gap from 3/2 to 10/7 for a superclass of these points for which a lower bound of 4/3 is proved. A key role in the proof of this result is played by finding Hamiltonian cycles whose existence is equivalent to Kotzig's result on compatible Eulerian tours, and which lead us to delta-matroids for developing the related algorithms. Our arguments also involve other innovative tools from combinatorial optimization with the potential of a broader use.