The Fréchet distance provides a way to measure similarity of curves and naturally lends itself to fundamental computational tasks, such as clustering, nearest-neighbor searching, and spherical range searching in the corresponding metric space. Finding provably efficient algorithms for these problems however poses an ongoing challenge---last but not least because the doubling dimension is infinite. I will talk about recent results on variants of k-center (and k-median) clustering under this distance measure with the additional restriction that the complexity of the centers is bounded by a parameter. In particular,
(1) There exists no polynomial-time approximation scheme unless P=NP, even if k=1 and even if the curves are embedded in the line.
(2) There exists a surprisingly simple 3-approximation scheme providing an almost tight approximation bound for curves embedded in the plane.
(3) Under certain conditions, there exists a near-linear-time (1+eps)-approximation algorithm, for any eps>0, for curves embedded in the line.
This is based on joint work with Kevin Buchin, Joachim Gudmundsson, Michael Horton, Irina Kostitsyna, Amer Krivosija, Maarten Löffler, Christian Sohler, and Martijn Struijs.

This talk surveys some recent progress on approximation algorithms for the path version of the traveling salesman problem. In this problem we are looking for a shortest tour through a given set of cities with fixed start- and endpoint. In contrast to the classical traveling salesman problem (TSP), the start and end of the tour might be different. While the best known approximation algorithm for TSP is still the classical Christofides algorithm from the 1970’s, a lot of progress has been made recently for the path version. In this talk we focus on our dynamic programming approach, which has been used in several algorithms: our 3/2+ε-approximation, Zenklusen's 3/2-approximation, and our new algorithm for unit-weight graphs. In this special case we know the exact integrality ratio, 3/2, but our approximation ratio is even better. This is joint work with Jens Vygen.