Séminaire Quaresmi ce 21 novembre: Problème de Correlation Clustering avec Médiateurs

Ce jeudi 21 novembre, le laboratoire Quaresmi accueillera Zacharie Ales de l’ENSTA-Paris-Tech, Rosa Figueiredo de l’Université d’Avignon. Avec Céline Engelbeen, ils proposeront un exposé intitulé « Problème de Correlation Clustering avec Médiateurs ».

Le problème de correlation clustering (CCP) consiste à partitionner les sommets d’un graphe afin que la somme des poids positifs entre les parties et la somme des poids négatifs à l’intérieur des parties soient minimales. Dans cette présentation, nous introduisons un nouveau problème de ce type dans lequel un ensemble de sommets appelés médiateurs doit également être identifié. Les médiateurs doivent avoir de bonnes relations les uns avec les autres. Par exemple, dans un contexte politique, un ensemble de médiateurs pourrait représenter un ensemble de députés chargés d’évaluer une loi.

Les propriété définies par les contraintes de notre problème sont non héréditaires et ce problème est NP-difficile. Nous présentons un programme linéaire en nombres entiers, un algorithme d’énumération ainsi que des résultats numériques préliminaires.

Séminaire ouvert à tous. La présentation aura lieu à l’ICHEC, site Anjou, local E103. Pour faciliter l’organisation, merci de vous inscrire auprès de  celine.engelbeen@ichec.be

Au plaisir de vous y voir nombreux.