le 17 octobre 2019 à 14:00
L’efficacité de la recherche locale
Nous présentons des schémas d’approximation en temps polynomial basés sur la recherche locale pour la localisation des installations, la k-médiane et la k-moyenne dans des graphes planaires ou dans des espaces euclidiens de dimension limitée, où le voisinage local d’une solution consiste à modifier les emplacements de quelques centres. Ceci peut être considéré comme une explication de l’efficacité des heuristiques de recherche locale dans la pratique. Ceci est basé sur un travail conjoint avec Vincent Cohen-Addad et Philip Klein.
En savoir plus...Amphi Ircica, Villeneuve d'Ascq
français
English