W&M Featured Events
This calendar presented by
William & Mary
[PAST EVENT] Mathematics Colloquium/CSUMS Lecture
March 16, 2012
3:30pm - 4:30pm
Title: The Subtour LP for the Traveling Salesman Problem
Abstract: The traveling salesman problem (TSP) is perhaps the most famous problem in combinatorial optimization: given a set of cities and the distances for traveling between each pair of cities, the goal of the problem is to find the shortest tour that visits each city exactly once and returns to its starting point. We consider TSP instances in which the distances are symmetric and obey the triangle inequality. Finding the optimal tour is known to be NP-hard; nevertheless, the past decades have seen great progress in solving real-world instances of the TSP. A starting point for solving real-world TSP instances is a linear programming relaxation called the subtour LP. The subtour LP is known to give excellent lower bounds on TSP instances in practice, coming within a percent or two of the length of the optimal tour. However, its theoretical worst-case is not well understood. Examples are known that show that the worst-case ratio is at least 4/3, and the famous Christofides' algorithm always finds a tour of length at most 3/2 times the value of the subtour LP. A long-standing conjecture states that the worst-case ratio, taken over all instances of the problem, of the value of the optimal tour to the value of the subtour LP is at most 4/3.
In the past two years, there has been a lot of exciting progress in this area. In this talk, we review some of the known results, and present some new results that refine our understanding of the subtour LP. 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 case in which all distances between cities are either 1 or 2. For these instances we show that the worst-case ratio of the value of the optimal tour to the value of the subtour LP is always strictly better than 4/3.
This is based on joint work with Jiawei Qian, Frans Schalekamp and David P. Williamson.
Abstract: The traveling salesman problem (TSP) is perhaps the most famous problem in combinatorial optimization: given a set of cities and the distances for traveling between each pair of cities, the goal of the problem is to find the shortest tour that visits each city exactly once and returns to its starting point. We consider TSP instances in which the distances are symmetric and obey the triangle inequality. Finding the optimal tour is known to be NP-hard; nevertheless, the past decades have seen great progress in solving real-world instances of the TSP. A starting point for solving real-world TSP instances is a linear programming relaxation called the subtour LP. The subtour LP is known to give excellent lower bounds on TSP instances in practice, coming within a percent or two of the length of the optimal tour. However, its theoretical worst-case is not well understood. Examples are known that show that the worst-case ratio is at least 4/3, and the famous Christofides' algorithm always finds a tour of length at most 3/2 times the value of the subtour LP. A long-standing conjecture states that the worst-case ratio, taken over all instances of the problem, of the value of the optimal tour to the value of the subtour LP is at most 4/3.
In the past two years, there has been a lot of exciting progress in this area. In this talk, we review some of the known results, and present some new results that refine our understanding of the subtour LP. 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 case in which all distances between cities are either 1 or 2. For these instances we show that the worst-case ratio of the value of the optimal tour to the value of the subtour LP is always strictly better than 4/3.
This is based on joint work with Jiawei Qian, Frans Schalekamp and David P. Williamson.
Contact
[[rrkinc, Rex Kincaid]]