Dynamic Programming Approximations for Traveling Salesman Problems
|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.
200 University Avenue West
Waterloo, ON N2L 3G1