The Traveling Salesman Problem under squared Euclidean distances

M.T. Berg, de, F.S.B. Nijnatten, van, R.A. Sitters, G.J. Woeginger, A. Wolff

Research output: Book/ReportReportAcademic

2 Citations (Scopus)


Let P be a set of points in Rd, and let a = 1 be a real number. We define the distance between two points p, q ¿ P as |pq|a, where |pq| denotes the standard Euclidean distance between p and q. We denote the traveling salesman problem under this distance function by Tsp(d,a). We design a 5-approximation algorithm for Tsp(2,2) and generalize this result to obtain an approximation factor of 3a-1 +v6a/3 for d = 2 and all a = 2. We also study the variant Rev-Tsp of the problem where the traveling salesman is allowed to revisit points. We present a polynomial-time approximation scheme for Rev-Tsp(2, a) with a = 2, and we show that Rev-Tsp(d,a) is apx-hard if d = 3 and a > 1. The apx-hardness proof carries over to Tsp(d, a) for the same parameter ranges.
Original languageEnglish
Number of pages12
Publication statusPublished - 2010

Publication series [cs.CG]


Dive into the research topics of 'The Traveling Salesman Problem under squared Euclidean distances'. Together they form a unique fingerprint.

Cite this