L’algorithme de recherche locale est un schéma d’approximation pour le placement d’installations dans un graphe planaire, et généralisationsClaire Mathieu (DI ENS Ulm, Paris)
We give the first polynomial-time approximation schemes (PTASs) for the following problems:
- uniform facility location in edge-weighted planar graphs;
- k -median and k -means in edge-weighted planar graphs;
- 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.