A PTAS for Euclidean TSP with hyperplane neighborhoods

Antonios Antoniadis, Krzysztof Fleszar, Ruben Hoeksma, Kevin Schewior

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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 [20], which gives rise to studying more tractable special cases of the problem. In this paper, 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 [16, 34] . While for d = 2 an exact algorithm with running time O(n5) is known [28], settling the exact approx-imability of the problem for d = 3 has been repeatedly posed as an open question [23, 24, 34, 40]. To date, only an approximation algorithm with guarantee exponential in d is known [24], 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 the optimal tour by a convex polytope of bounded complexity. Such polytopes are represented as solutions of a sophisticated LP formulation, which we combine with the enumeration of crucial properties 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 to transform an arbitrary convex polytope into one with a constant number of vertices and, in turn, into one of bounded complexity in the above sense. Hereby, we maintain important properties of the polytope.

Original languageEnglish
Title of host publicationACM-SIAM Symposium on Discrete Algorithms
PublisherACM Publishing
Pages1089-1105
Number of pages17
ISBN (Electronic)978-1-61197-548-2
DOIs
Publication statusPublished - 2019
Externally publishedYes

Fingerprint

Polynomial Time Approximation Scheme
Hyperplane
Euclidean
Polynomials
Approximation algorithms
Oils and fats
Convex Polytope
Polytopes
Hardness
NP-hardness
Euclidean plane
Arbitrary
Exact Algorithms
Approximation
Approximation Scheme
Polytope
Convex Hull
Enumeration
Search Space
Euclidean space

Cite this

Antoniadis, A., Fleszar, K., Hoeksma, R., & Schewior, K. (2019). A PTAS for Euclidean TSP with hyperplane neighborhoods. In ACM-SIAM Symposium on Discrete Algorithms (pp. 1089-1105). ACM Publishing. https://doi.org/10.1137/1.9781611975482.67
Antoniadis, Antonios ; Fleszar, Krzysztof ; Hoeksma, Ruben ; Schewior, Kevin. / A PTAS for Euclidean TSP with hyperplane neighborhoods. ACM-SIAM Symposium on Discrete Algorithms. ACM Publishing, 2019. pp. 1089-1105
@inproceedings{b3c049587657485a9102cb7a00e6efce,
title = "A PTAS for Euclidean TSP with hyperplane neighborhoods",
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 [20], which gives rise to studying more tractable special cases of the problem. In this paper, 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 [16, 34] . While for d = 2 an exact algorithm with running time O(n5) is known [28], settling the exact approx-imability of the problem for d = 3 has been repeatedly posed as an open question [23, 24, 34, 40]. To date, only an approximation algorithm with guarantee exponential in d is known [24], 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 the optimal tour by a convex polytope of bounded complexity. Such polytopes are represented as solutions of a sophisticated LP formulation, which we combine with the enumeration of crucial properties 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 to transform an arbitrary convex polytope into one with a constant number of vertices and, in turn, into one of bounded complexity in the above sense. Hereby, we maintain important properties of the polytope.",
author = "Antonios Antoniadis and Krzysztof Fleszar and Ruben Hoeksma and Kevin Schewior",
year = "2019",
doi = "10.1137/1.9781611975482.67",
language = "English",
pages = "1089--1105",
booktitle = "ACM-SIAM Symposium on Discrete Algorithms",
publisher = "ACM Publishing",

}

Antoniadis, A, Fleszar, K, Hoeksma, R & Schewior, K 2019, A PTAS for Euclidean TSP with hyperplane neighborhoods. in ACM-SIAM Symposium on Discrete Algorithms. ACM Publishing, pp. 1089-1105. https://doi.org/10.1137/1.9781611975482.67

A PTAS for Euclidean TSP with hyperplane neighborhoods. / Antoniadis, Antonios; Fleszar, Krzysztof; Hoeksma, Ruben; Schewior, Kevin.

ACM-SIAM Symposium on Discrete Algorithms. ACM Publishing, 2019. p. 1089-1105.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - A PTAS for Euclidean TSP with hyperplane neighborhoods

AU - Antoniadis, Antonios

AU - Fleszar, Krzysztof

AU - Hoeksma, Ruben

AU - Schewior, Kevin

PY - 2019

Y1 - 2019

N2 - 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 [20], which gives rise to studying more tractable special cases of the problem. In this paper, 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 [16, 34] . While for d = 2 an exact algorithm with running time O(n5) is known [28], settling the exact approx-imability of the problem for d = 3 has been repeatedly posed as an open question [23, 24, 34, 40]. To date, only an approximation algorithm with guarantee exponential in d is known [24], 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 the optimal tour by a convex polytope of bounded complexity. Such polytopes are represented as solutions of a sophisticated LP formulation, which we combine with the enumeration of crucial properties 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 to transform an arbitrary convex polytope into one with a constant number of vertices and, in turn, into one of bounded complexity in the above sense. Hereby, we maintain important properties of the polytope.

AB - 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 [20], which gives rise to studying more tractable special cases of the problem. In this paper, 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 [16, 34] . While for d = 2 an exact algorithm with running time O(n5) is known [28], settling the exact approx-imability of the problem for d = 3 has been repeatedly posed as an open question [23, 24, 34, 40]. To date, only an approximation algorithm with guarantee exponential in d is known [24], 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 the optimal tour by a convex polytope of bounded complexity. Such polytopes are represented as solutions of a sophisticated LP formulation, which we combine with the enumeration of crucial properties 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 to transform an arbitrary convex polytope into one with a constant number of vertices and, in turn, into one of bounded complexity in the above sense. Hereby, we maintain important properties of the polytope.

U2 - 10.1137/1.9781611975482.67

DO - 10.1137/1.9781611975482.67

M3 - Conference contribution

AN - SCOPUS:85066953198

SP - 1089

EP - 1105

BT - ACM-SIAM Symposium on Discrete Algorithms

PB - ACM Publishing

ER -

Antoniadis A, Fleszar K, Hoeksma R, Schewior K. A PTAS for Euclidean TSP with hyperplane neighborhoods. In ACM-SIAM Symposium on Discrete Algorithms. ACM Publishing. 2019. p. 1089-1105 https://doi.org/10.1137/1.9781611975482.67