English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  A PTAS for Euclidean TSP with Hyperplane Neighborhoods

Antoniadis, A., Fleszar, K., Hoeksma, R., & Schewior, K. (2018). A PTAS for Euclidean TSP with Hyperplane Neighborhoods. Retrieved from http://arxiv.org/abs/1804.03953.

Item is

Basic

show hide
Genre: Paper
Latex : A {PTAS} for {E}uclidean {TSP} with Hyperplane Neighborhoods

Files

show Files
hide Files
:
arXiv:1804.03953.pdf (Preprint), 242KB
Name:
arXiv:1804.03953.pdf
Description:
File downloaded from arXiv at 2018-12-06 12:33
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Antoniadis, Antonios1, Author           
Fleszar, Krzysztof2, Author
Hoeksma, Ruben2, Author
Schewior, Kevin2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: Computer Science, Data Structures and Algorithms, cs.DS
 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, 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.
While for $d=2$ an exact algorithm with running time $O(n^5)$ is known,
settling the exact approximability of the problem for $d=3$ has been repeatedly
posed as an open question. To date, only an approximation algorithm with
guarantee exponential in $d$ is known, 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.

Details

show
hide
Language(s):
 Dates: 2018-04-112018
 Publication Status: Published online
 Pages: 21 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1804.03953
URI: http://arxiv.org/abs/1804.03953
BibTex Citekey: Antoniadis_arXiv1804.03953
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show