A Proof of the Boyd-Carr Conjecture

Frans Schalekamp, David P. Williamson, Anke van Zuylen

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

Guest: Anke Van Zuylen
Host: Zvi Lotker

Leave a Reply

Your email address will not be published.

162,101 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>