2026-07-22T11:26:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2458 2024-03-06T10:33:23Z ddc:004 open_access

The Traveling Salesman Problem under Squared Euclidean Distances van Nijnatten, Fred Sitters, René Woeginger, Gerhard J. Wolff, Alexander de Berg, Mark Geometric traveling salesman problem power-assignment in wireless networks distance-power gradient NP-hard APX-hard 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fred van Nijnatten and René Sitters and Gerhard J. Woeginger and Alexander Wolff and Mark de Berg 2010 Is Part Of LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2010.2458 urn:nbn:de:0030-drops-24580 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2458 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode