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
call.
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.