Name
Abstract | ||
|---|---|---|
Determining the precise integrality gap for the subtour 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 [3] 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 a fractional 2-matching has no cut edge, we can further prove that an optimal 2-matching is at most 10/9 times the cost of the fractional 2-matching. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.5555/2095116.2095233 | symposium on discrete algorithms |
Keywords | DocType | Volume |
cut edge,salesman problem,obey triangle inequality,fractional 2-matching,precise integrality gap,boyd-carr conjecture,general case,subtour lp,optimal 2-matching,subtour lp relaxation,lp relaxation,upper bound,traveling salesman problem,data structure,triangle inequality | Conference | abs/1107.1628 |
ISBN | Citations | PageRank |
978-1-61197-251-1 | 4 | 0.41 |
References | Authors | |
13 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frans Schalekamp | 1 | 76 | 7.91 |
| David P. Williamson | 2 | 3564 | 413.34 |
| Anke Van Zuylen | 3 | 291 | 22.10 |