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 |
Abstract:
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.