Tuesday, 13:45 - 14:10 h, Room: H 3010


Anke van Zuylen
A proof of the Boyd-Carr conjecture

Coauthors: Frans Schalekamp, David P. Williamson


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 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.


Talk 2 of the invited session Tue.2.H 3010
"Travelling salesman problem I" [...]
Cluster 1
"Approximation & online algorithms" [...]


  Payday Loans In Tennessee. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra influence on blood clots.