Bonjour à tous,

Vous êtes tous et toutes cordialement invité.es à assister à la présentation de projet du prédoc III de Xuan Kien Phung, le 20 août à 15h30

Titre : Études théoriques et algorithmiques du problème de Kemeny et son interaction avec les autres domaines scientifiques et sociaux.

Date: mercredi 20 août à 15h30.

Location: Pavillon André-Aisenstadt, salle 1409, 2920 Chemin de la Tour

Jury

Résumé

Soit un ensemble de classements (votes) complets. Le problème de médiane de Kemeny (appelé aussi Kemeny Rank Aggregation Problem) est un problèmed'optimisation combinatoire qui consiste à calculer les classements appelésmédianes qui sont les meilleurs consensus par rapport à la certainedistance de Kendall-tau qui mesure le nombre de paires en désaccord entredeux classements. Une médiane est donc un classement dont la distance àl'ensemble des votes est minimale. Les médianes admettent des propriétésaxiomatiques désirées et  plusieurs  applications en bio-informatique, enthéorie du choix social, en théorie de décision en apprentissageautomatique. Or, le problème de médiane de Kemeny est NP-difficile. Notreprojet de doctorat consiste  à obtenir dans un premier temps des propriétésquantitatives et de nouvelles techniques de réduction d'espace de recherchedes médianes en établissant des contraintes sur plusieurs sous-ensemblesdes candidats. On étudie dans un deuxième temps les applications des cesméthodes obtenues dans le but d'accélérer la résolution exacte ou
approximative du problème de médiane ainsi que la résolution des problèmesadjacents.