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" [...]


  USA Payday Loans Online. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.