[Colloq] (Colloq) Stable matching in practice Speaker: Claire Mathieu, Wednesday 10/31, 12pm 366WVH

[Ponte, Christopher]

Title: Stable matching in practice

Speaker: Claire Mathieu, CNRS, Paris, France

When: Wed, Oct 31, 12 noon 366 WVH

Abstract: 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.

Bio: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.