when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-24580
URL:

; ; ; ;

### The Traveling Salesman Problem under Squared Euclidean Distances

 pdf-format:

### Abstract

Let $P$ be a set of points in $\Reals^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\ge2$. 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\ge2$, and we show that Rev-\tsp$(d, \alpha)$ is \apx-hard if $d\ge3$ and $\alpha>1$. The \apx-hardness proof carries over to \tsp$(d, \alpha)$ for the same parameter ranges.

### BibTeX - Entry

@InProceedings{vannijnatten_et_al:LIPIcs:2010:2458,
author =	{Fred van Nijnatten and Ren{\'e} Sitters and Gerhard J. Woeginger and Alexander Wolff and Mark de Berg},
title =	{{The Traveling Salesman Problem under Squared Euclidean Distances}},
booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
pages =	{239--250},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-16-3},
ISSN =	{1868-8969},
year =	{2010},
volume =	{5},
editor =	{Jean-Yves Marion and Thomas Schwentick},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},