- Series
- ACO Colloquium
- Time
- Tuesday, October 11, 2011 - 11:00am for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- David P. Williamson – Cornell University and TU Berlin – dpw@cs.cornell.edu
- Organizer
- Prasad Tetali
Please Note: Refreshments at 10:30am in the atrium outside Skiles 006
The traveling salesman problem (TSP) is the most famous problem in
discrete optimization. Given $n$ cities and the costs $c_{ij}$ for
traveling from city $i$ to city $j$ for all $i,j$, the goal of the
problem is to find the least expensive tour that visits each city
exactly once and returns to its starting point. We consider cases in
which the costs are symmetric and obey the triangle inequality. In
1954, Dantzig, Fulkerson, and Johnson introduced a linear programming
relaxation of the TSP now known as the subtour LP, and used it to find
the optimal solution to a 48-city instance. Ever since then, the
subtour LP has been used extensively to find optimal solutions to TSP
instances, and it is known to give extremely good lower bounds on the
length of an optimal tour.
Nevertheless, the quality of the subtour LP bound is poorly understood
from a theoretical point of view. For 30 years it has been known that
it is at least 2/3 times the length of an optimal tour for all instances
of the problem, and it is known that there are instances such that it
is at most 3/4 times the length of an optimal tour, but no progress has
been made in 30 years in tightening these bounds.
In this talk we will review some of the results that are known about the
subtour LP, and give some new results that refine our understanding in
some cases. In particular, we resolve a conjecture of Boyd and Carr
about the ratio of an optimal 2-matching to the subtour LP bound in the
worst case. We also begin a study of the subtour LP bound for the
extremely simple case in which all costs $c_{ij}$ are either 1 or 2.
For these instances we can show that the subtour LP is always strictly
better than 3/4 times the length of an optimal tour.
These results are joint work with Jiawei Qian, Frans Schalekamp, and Anke van Zuylen.