Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:A PTAS for TSP with Hyperplane Neighborhoods
Speaker:Antonios Antoniadis
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 8 March 2018
Duration:30 Minutes
Building:E1 4
In the Traveling Salesman 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 talk, we focus on regions that are hyperplanes in the $d$-dimensional Euclidean space. 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 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.

We believe that both the LP formulation representing polytopes of adjustable complexity and the sparsification techniques are of independent interest.

Name(s):Antonios Antoniadis
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Antonios Antoniadis, 02/20/2018 09:20 AM
Last modified:
Uwe Brahm/MPII/DE, 03/08/2018 07:01 AM
  • Antonios Antoniadis, 02/20/2018 09:20 AM -- Created document.