Campus Event Calendar
Event Entry
What and Who
The Subtour LP for the Traveling Salesman Problem (A Proof of the Boyd-Carr Conjecture)
Anke van Zuylen
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 25 October 2011
13:00
30 Minutes
E1 4
024
Saarbrücken
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 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 talk, we resolve the Boyd-Carr conjecture.
This is joint work with Frans Schalekamp and David P. Williamson.
Contact
Anke Van Zuylen
--email hidden
passcode not visible
logged in users only
Anke Van Zuylen, 10/20/2011 12:56 -- Created document.