Universität zu Köln

Antoniadis, Antonios ORCID: 0000-0003-2152-7883, Fleszar, Krzysztof, Hoeksma, Ruben ORCID: 0000-0002-6553-7242 and Schewior, Kevin ORCID: 0000-0003-2236-0210 (2020). A PTAS for Euclidean TSP with Hyperplane Neighborhoods. ACM Trans. Algorithms, 16 (3). NEW YORK: ASSOC COMPUTING MACHINERY. ISSN 1549-6333

Full text not available from this repository.

Abstract

In the Traveling Salesperson Problem with Neighborhoods (TSPN), we are given a collection of geometric regions in some space. The goal is to output a tour of minimum length that visits at least one point in each region. Even in the Euclidean plane, TSPN is known to be APX-hard [ 27], which gives rise to studying more tractable special cases of the problem. In this article, we focus on the fundamental special case of regions that are hyperplanes in the d-dimensional Euclidean space. This case contrasts the much-better understood case of so-called fat regions [20, 40]. While for d = 2, an exact algorithm with a running time of O(n(5)) is known [34], settling the exact approximability of the problem for d = 3 has been repeatedly posed as an open question [29, 30, 40, 47]. To date, only an approximation algorithm with guarantee exponential in d is known [30], and NP-hardness remains open. For arbitrary fixed d, we develop a Polynomial Time Approximation Scheme (PTAS) that works for both the tour and path version of the problem. Our algorithm is based on approximating the convex hull of an optimal tour by a convex polytope of bounded complexity. After enumerating a number of structural properties of these polytopes, a linear program finds one of them that minimizes the length of the tour. As the approximation guarantee approaches 1, our scheme adjusts the complexity of the considered polytopes accordingly. In the analysis of our approximation scheme, we show that our search space includes a sufficiently good approximation of the optimum. To do so, we develop a novel and general sparsification technique that transforms an arbitrary convex polytope into one with a constant number of vertices, and, subsequently, into one of bounded complexity in the above sense. We show that this transformation does not increase the tour length by too much, while the transformed tour visits any hyperplane that it visited before the transformation.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Antoniadis, Antonios UNSPECIFIED orcid.org/0000-0003-2152-7883 UNSPECIFIED Fleszar, Krzysztof UNSPECIFIED UNSPECIFIED UNSPECIFIED Hoeksma, Ruben UNSPECIFIED orcid.org/0000-0002-6553-7242 UNSPECIFIED Schewior, Kevin UNSPECIFIED orcid.org/0000-0003-2236-0210 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-330880
DOI:	10.1145/3383466
Journal or Publication Title:	ACM Trans. Algorithms
Volume:	16
Number:	3
Date:	2020
Publisher:	ASSOC COMPUTING MACHINERY
Place of Publication:	NEW YORK
ISSN:	1549-6333
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language TRAVELING SALESMAN PROBLEM; APPROXIMATION ALGORITHMS; TIME Multiple languages Computer Science, Theory & Methods; Mathematics, Applied Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/33088