2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture

• 成果类型: Article
• 署名作者: Schalekamp, Frans; Williamson, David P.; van Zuylen, Anke
• 署名单位: William & Mary; Cornell University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2013.0608
• 发表日期: 2014
• 页码: 403-417
• 关键词: integrality gap; tsp

摘要

Determining the precise integrality gap for the subtour linear programming (LP) relaxation of the traveling salesman problem is a significant open question, with little progress made in thirty years in the general case of symmetric costs that obey triangle inequality. Boyd and Carr [Boyd S, Carr R (2011) Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices. Discrete Optim. 8:525-539. Prior version accessed June 27, 2011, http://www.site.uottawa.ca/(similar to)sylvia/recentpapers/halftri.pdf.] observe that we do not even know the worst-case upper bound on the ratio of the optimal 2-matching to the subtour LP; they conjecture the ratio is at most 10/9. In this paper, we prove the Boyd-Carr conjecture. In the case that the support of a fractional 2-matching has no cut edge, we can further prove that an optimal 2-matching has cost at most 10/9 times the cost of the fractional 2-matching.