Linear Programming Relaxations for the TSP

Linear Programming Relaxations for the TSP

-
William Cook, Georgia Institute of Technology
Fine Hall 224

The most successful solution approaches to the traveling salesman problem are based on lower bounds obtained from linear programming relaxations. We will discuss a number of open problems concerning this approach, with emphasis on topics that could improve the practical performance of LP-based algorithms.