Claire Mathieu (DI ENS Ulm, Paris)

We give the first polynomial-time approximation schemes (PTASs) for the following problems:

  1. uniform facility location in edge-weighted planar graphs;
  2. k -median and k -means in edge-weighted planar graphs;
  3. k -means in Euclidean space of bounded dimension.

The algorithm is local search where the local neighborhood of a solution S consists of all solutions obtained from S by removing or adding a few centers. This is joint work with Vincent Cohen-Addad and Philip Klein.