Paper Info
Title
2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture.
Abstract
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.
Year
DOI
Venue
2014
10.1287/moor.2013.0608
MATHEMATICS OF OPERATIONS RESEARCH
Keywords
DocType
Volume
traveling salesman problem,subtour elimination,linear programming,integrality gap,2-matching,fractional 2-matching
Journal
39
Issue
ISSN
Citations 
2
0364-765X
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Frans Schalekamp1767.91
David P. Williamson23564413.34
Anke Van Zuylen329122.10