The traveling salesman problem
Yair BartalHebrew University, Jerusalem, IsraelLee-Ad GottliebHebrew University, Jerusalem, IsraelRobert KrauthgamerWeizmann Institute, Rehovot, Israel
2012en
ABI
Аннотация
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.
Ҳали таржима қилинмаган
Идентификаторлар
Иқтибослар ва манбалар
2 та иқтибос0 та фойдаланилган манба