Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 20 Septembre 2016

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

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

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr