The traveling salesman problem
Yair BartalHebrew University, Jerusalem, IsraelLee-Ad GottliebHebrew University, Jerusalem, IsraelRobert KrauthgamerWeizmann Institute, Rehovot, Israel
2012en
ABI
Annotatsiya
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.
Hali tarjima qilinmagan
Identifikatorlar
Iqtiboslar va manbalar
2 ta iqtibos0 ta foydalanilgan manba