The traveling salesman problem
Yair BartalHebrew University, Jerusalem, IsraelLee-Ad GottliebHebrew University, Jerusalem, IsraelRobert KrauthgamerWeizmann Institute, Rehovot, Israel
2012en
ABI
Abstract
The Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. We design for this problem a randomized polynomial-time algorithm that computes a (1+µ)-approximation to the optimal tour, for any fixed µ>0, in TSP instances that form an arbitrary metric space with bounded intrinsic dimension.
Identifiers
Citations and references
Cited by 20 references