L’algorithme de recherche locale est un schéma d’approximation pour le placement d’installations dans un graphe planaire, et généralisations

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.