https://hal.inria.fr/inria-00455193de Berg, MarkMarkde BergDepartment of mathematics and computing science [Eindhoven] - TU/e - Eindhoven University of Technology [Eindhoven]van Nijnatten, FredFredvan NijnattenDepartment of mathematics and computing science [Eindhoven] - TU/e - Eindhoven University of Technology [Eindhoven]Sitters, ReneReneSittersFaculty of Economics and Business Administration, - VU - Vrije Universiteit Amsterdam [Amsterdam]J. Woeginger, GerhardGerhardJ. WoegingerDepartment of mathematics and computing science [Eindhoven] - TU/e - Eindhoven University of Technology [Eindhoven]Wolff, AlexanderAlexanderWolffLehrstuhl für Informatik I [Würzburg] - JMU - Julius-Maximilians-Universität Würzburg [Wurtzbourg, Allemagne]The Traveling Salesman Problem Under Squared Euclidean DistancesHAL CCSD2010Geometric traveling salesman problempower-assignment in wireless networksdistance-power gradientNP-hardAPX-hard[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG][INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC]Loria, PublicationsJean-Yves Marion and Thomas Schwentick2010-02-09 16:48:492021-09-17 14:50:092010-02-09 16:50:48enConference papersapplication/pdf1Let $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.