The Traveling Salesman Problem Under Squared Euclidean Distances

Abstract

Let $P$ be a set of points in ${\mathbb{R}}^d$, and let $\alpha \ge 1$ be a real number. We define the distance between two points $p,q\in P$ as $|pq{|}^{\alpha }$, where $|pq|$ denotes the standard Euclidean distance between $p$ and $q$. We denote the traveling salesman problem under this distance function by TSP($d,\alpha$). We design a 5-approximation algorithm for TSP(2,2) and generalize this result to obtain an approximation factor of $3^{\alpha -1}+{\sqrt{6}}^{\alpha }/3$ for $d=2$ and all $\alpha \ge 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,\alpha )$ with $\alpha \ge 2$, and we show that Rev-TSP$(d,\alpha )$ is APX-hard if $d\ge 3$ and $\alpha >1$. The APX-hardness proof carries over to TSP$(d,\alpha )$ for the same parameter ranges.

12 pages, 4 figures. (v2) Minor linguistic changes