The traveling salesman problem: Low-dimensionality implies a polynomial time approximation scheme

Yair Bartal, Lee Ad Gottlieb, Robert Krauthgamer

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

42 ציטוטים ‏(Scopus)

תקציר

The traveling salesman problem (TSP) is among the most famous NP-hard optimization problems. We design for this problem an algorithm that for any fixed ∈ >0 computes in randomized polynomial time a (1 + ∈)-approximation to the optimal tour in TSP instances that form an arbitrary metric space with bounded intrinsic dimension. The celebrated results of Arora [J. ACM, 45 (1998), pp. 753-782] and Mitchell [SIAM J. Comput., 28 (1999), pp. 1298-1309] prove that the above result holds in the special case of TSP in a fixed-dimensional Euclidean space. Thus, our algorithm demonstrates that the algorithmic tractability of metric TSP depends on the dimensionality of the space and not on its specific geometry. This result resolves a problem that has been open since the quasi-polynomial time algorithm of Talwar [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 281-290].

שפה מקוריתאנגלית
עמודים (מ-עד)1563-1581
מספר עמודים19
כתב עתSIAM Journal on Computing
כרך45
מספר גיליון4
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2016

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'The traveling salesman problem: Low-dimensionality implies a polynomial time approximation scheme'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי