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\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.
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/inria-00455193
Contributor : Publications Loria <>
Submitted on : Tuesday, February 9, 2010 - 4:48:49 PM
Last modification on : Wednesday, October 10, 2018 - 8:44:13 PM
Long-term archiving on : Friday, June 18, 2010 - 6:10:21 PM

File

deberg.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00455193, version 1

Collections

Citation

Mark de Berg, Fred van Nijnatten, Rene Sitters, Gerhard J. Woeginger, Alexander Wolff. The Traveling Salesman Problem Under Squared Euclidean Distances. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Inria Nancy Grand Est & Loria, Mar 2010, Nancy, France. pp.239-250. ⟨inria-00455193⟩

Share

Metrics

Record views

181

Files downloads

279