Tutte seminar - Alejandro Toriello

Friday, May 10, 2013 3:30 pm - 4:30 pm EDT (GMT -04:00)

Dynamic Programming Approximations for Traveling Salesman Problems

Speaker: Alejandro Toriello
Affiliation: USC
Room: Mathematics and Computer Building (MC) 5158


We propose a framework of lower bounds for the asymmetric traveling salesman problem (TSP) based on approximating the dynamic programming formulation with basis vector sets. We discuss how various well-known lower bounds correspond to intuitive basis choices, then introduce a new family of successively tighter, polynomially solvable polyhedral bounds. We show that the base member of this family is equivalent to the Held-Karp bound and discuss how it can be modified to provide bounds for several TSP variants. Time permitting, we discuss other applications and extensions of this methodology.