moteur de recherche

Séminaire Algo - Sylvie Hamel
Séminaire Algo - Sylvie Hamel
23-oct.-2018 14:00
Il y a: 53 days





Sylvie Hamel

Médiane de permutations: réduction d’espace et lien avec le 3-Hitting Set Problem

Salle 27 - Bâtiment Lavoisier

Le problème de la médiane d’un ensemble de permutations est un problème d’optimisation combinatoire qui consiste à trouver une permutation, appelée médiane, qui minimise la somme des distances de celle-ci aux permutations de l’ensemble. 

Dans cet exposé, c’est la distance de Kendall-tau qui sera utilisée. Cette distance compte le nombre de paires d’éléments dont l’ordre relatif est en désaccord entre deux permutations. Sous cette distance, le problème de la médiane a été démontré NP-difficile, même pour de petits ensembles ne contenant que 4 permutations. Je parlerai dans cet exposé de méthodes efficaces de réduction d’espace pour ce problème de même que d’un lien intéressant avec le 3-Hitting Set Problem. 

Les travaux présentés dans cet exposé ont été réalisés en collaboration avec Robin Milosz (Université de Montréal) et Adeline Pierrot (LRI, Université Paris-Sud).








<- retour: