- Series
- Combinatorics Seminar
- Time
- Friday, February 7, 2020 - 3:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Wesley Pegden – Carnegie Mellon University
- Organizer
- 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.