Tutte seminar - Alejandro Toriello

Dynamic Programming Approximations for Traveling Salesman Problems

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.