On the integrality gap of the subtour LP for the 1,2-TSP

• 成果类型: Article; Proceedings Paper
• 署名作者: Qian, Jiawei; Schalekamp, Frans; Williamson, David P.; van Zuylen, Anke
• 署名单位: William & Mary; Cornell University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0835-4
• 发表日期: 2015
• 页码: 131-151
• 关键词: traveling salesman problem; tsp

摘要

In this paper, we study the integrality gap of the subtour LP relaxation for the traveling salesman problem in the special case when all edge costs are either 1 or 2. For the general case of symmetric costs that obey triangle inequality, a famous conjecture is that the integrality gap is 4/3. Little progress towards resolving this conjecture has been made in 30 years. We conjecture that when all edge costs , the integrality gap is 10/9. We show that this conjecture is true when the optimal subtour LP solution has a certain structure. Under a weaker assumption, which is an analog of a recent conjecture by Schalekamp et al., we show that the integrality gap is at most 7/6. When we do not make any assumptions on the structure of the optimal subtour LP solution, we can show that integrality gap is at most 5/4; this is the first bound on the integrality gap of the subtour LP strictly less than 4/3 known for an interesting special case of the TSP. We show computationally that the integrality gap is at most 10/9 for all instances with at most 12 cities.