Graduate Seminar - 4/10, 12:00PM Duncan Hall 1064

Caleb Fast

"An Approach to the 4/3 Conjecture for the Traveling Salesman Problem"

This talk develops an approach for determining the precise strength of the subtour relaxation of the Traveling Salesman Problem. The Traveling Salesman Problem (TSP) arises in fields ranging from route planning, to manufacturing, to genetics. Better solutions to this problem will reduce operating costs across a diverse spectrum of industries. The subtour relaxation is important because it provides lower bounds on the optimal TSP tour and forms the core of cutting plane solution techniques. This talk will give sufficient conditions under which I show an improved bound on the integrality gap of the relaxation and which motivate future directions for this problem. My approach is also constructive, and could be used to motivate an improved approximation heuristic for the TSP.