Euclidean TSP with few inner points in linear space

Event type: 
HIIT seminar
Event time: 
17.10.2014 - 10:15 - 11:15
Lecturer : 
Pawel Gawrychowski
Exactum B222

Title: Euclidean TSP with few inner points in linear space

Abstract: Given a set of n points in the Euclidean plane, such that just k
points are strictly inside the convex hull of the whole set, we want
to find the shortest tour visiting every point. The fastest known
algorithm for the version with few inner points, i.e., small k, works
in O(k^O(k^0.5) k^1.5 n^3) time [Knauer and Spillner, WG 2006], but
also requires space of similar order, while the best linear space
algorithm takes O(k! k n) time [Deineko, Hoffmann, Okamoto, Woeginer,
Oper. Res. Lett. 34(1), 106-110]. We construct a linear space O(nk^2 +
k^O(k^0.5)) time algorithm. The new insight is extending the known
divide-and-conquer method based on planar separators with a
matching-based argument to shrink the instance in every recursive

About the presenter: Pawel Gawrychowski is currently a post-doc at the Max Planck Institute
for Informatics in Saarbruecken and will soon move to the University
of Warsaw.  He received his PhD in 2011 from the University of Wroclaw
for work on pattern matching in compressed texts that he presented at
SODA, ESA and STACS.  He has won the Best Student Paper award at
IWOCA, MFCS, ESA and CPM and the best paper award at CIAA.  In
addition to research, he has coached three teams to the ICPC finals.

15.10.2014 - 13:26 Sotiris Tasoulis
15.10.2014 - 13:26 Sotiris Tasoulis