A PTAS for TSP with hyperplane neighborhoods

Prelegent(ci)

Krszysztof Fleszar

Afiliacja

Univerisity of Warsaw

Termin

29 listopada 2018 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

A PTAS for TSP with hyperplane neighborhoods

In TSP with neighborhoods, we are asked for a shortest tour visiting a
given set of regions (i.e., neighborhoods).
When the neighborhoods are lines in 2D, the problem is efficiently
solvable. The problem becomes NP-hard for lines in 3D.
What about planes in 3D, or more generally, hyperplanes in higher
dimensions d? Is this case NP-hard? What is its approximability?
Prior to our work, only a recent (2^d)-approximation algorithm was known.

In this talk, we make a step forward in answering this repeatedly posed
open question by designing a PTAS. In a high-level view, we will see the
underlying ideas, including a novel sparsification technique for
polytopes of independent interest and a nice simple LP that will compute
our shortest tour.

Co-authors: Antonios Antoniadis, Ruben Hoeksma and Kevin Schewior [SODA
2019]

---