Fumei Lam
Massachusetts Institute of Technology
Friday, October 14, 2005
1:30 – 3:00 pm
Room 151
Traveling Salesman Path Problems
In the Traveling Salesman Path Problem, we are given a set of cities, traveling costs between city pairs and fixed source and destination cities. The objective is to find a minimum cost path from the source to destination visiting all cities exactly once. The problem is a generalization of the Traveling Salesman Problem with many important applications.
We’ll survey approximation algorithms for this problem and present properties of the polytope corresponding to a linear programming relaxation. We consider the set of traveling salesman path perfect graphs, graphs for which the convex hull of incidence vectors of traveling salesman paths can be described by linear inequalities. We show such graphs have a description by way of forbidden minors and also characterize them constructively. We extend these results to relate the underlying graph structure to the integrality gap of the corresponding fractional path polyhedron.
Joint work with Michel Goemans, Alantha Newman, and Santosh Vempala.
