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.
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.239-250, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00455193
Contributeur : Publications Loria <>
Soumis le : mardi 9 février 2010 - 16:48:49
Dernière modification le : mardi 9 février 2010 - 16:50:48
Document(s) archivé(s) le : vendredi 18 juin 2010 - 18:10:21

Fichier

deberg.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.239-250, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00455193〉

Partager

Métriques

Consultations de la notice

163

Téléchargements de fichiers

159