Colloquium du laboratoire Dieudonné - lundi 12 novembre 2018 à 14:30

La prochaine séance du Colloquium du laboratoire Dieudonné aura lieu le lundi 12 novembre à 14:30 en salle de conférences. Elle sera suivie d'une pause-café en salle café. Notre conférencière sera :

Claire MATHIEU (CNRS, École Normale Supérieure, Département d'Informatique, INRIA, Paris, Professeur au Collège de France sur la Chaire annuelle "Informatique et Sciences Numériques" en 2017/2018, https://www.di.ens.fr/ClaireMathieu.html)

et le titre de son exposé sera :

'Stable Matching in Practice'.

Un résumé est le suivant.

Stable matching methods, based on the algorithm designed by Gale and Shapley, are used around the world in many applications such as college admissions. Several criteria measure the quality of the result: number of students assigned; rank of the college assigned to the applicant in their preference list; robustness; running time; etc.

After reviewing properties of the algorithm in the pure, ideal setting, we present issues arising in practice. The input data is uncertain and evolves with time, so a one-shot algorithm does not suffice. It is not feasible for admission committees to meet continuously, so the process cannot be fully dynamic. To reconcile those competing constraints, a hybrid implementation proceeding partly online on the student side was recently proposed for college admissions in France. The system also incorporates side constraints on joint assignment to schools and to dorms.

About the Speaker

Claire MATHIEU does research on the design and analysis of algorithms, with a focus on approximation algorithms, particularly approximation schemes for NP-hard problems. A former student of Ecole normale supérieure, she received a PhD in Computer Science in 1988 at Paris-Sud University. She has held research and faculty positions at CNRS, Paris-Sud University, Ecole Polytechnique, Brown University, and Collège de France. She is currently a CNRS research director in Paris, France.

About the talk

It concerns the heart of the PARCOURSUP algorithm recently conceived by Claire MATHIEU and her collaborator Hugo GIMBERT.

Venez Nombreux !

L'équipe Colloquium