A PTAS for TSP with hyperplane neighborhoods

Speaker(s)

Krszysztof Fleszar

Affiliation

Univerisity of Warsaw

Date

Nov. 29, 2018, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

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]

---