Scalefree hardness of the Euclidean TSP

Combinatorics Seminar
Friday, February 7, 2020 - 3:05pm for 1 hour (actually 50 minutes)
Skiles 005
Wesley Pegden – Carnegie Mellon University
Prasad Tetali

We  show  that  if  $P\neq NP$,  then  a  wide  class  of  TSP heuristics fail to approximate the length of the TSP to asymptotic 
optimality, even for random Euclidean instances.  Previously, this result was not even known for any heuristics (greedy, etc) used in practice.  As an application, we show that when  using  a  heuristic from  this  class,  a  natural  class  of  branch-and-bound algorithms takes exponential time to find an optimal tour (again, even on a random point-set),  regardless  of  the  particular  branching  strategy  or lower-bound algorithm used.