TY - BOOK

T1 - The Traveling Salesman Problem under squared Euclidean distances

AU - Berg, de, M.T.

AU - Nijnatten, van, F.S.B.

AU - Sitters, R.A.

AU - Woeginger, G.J.

AU - Wolff, A.

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

M3 - Report

T3 - arXiv.org [cs.CG]

BT - The Traveling Salesman Problem under squared Euclidean distances

PB - s.n.

ER -