Ugo Bolletta : ugo.bolletta[at]univ-amu.fr
Mathieu Faure : mathieu.faure[at]univ-amu.fr
Centralised matching schemes have been established since 1952 to allocate residents to hospitals, students to schools/universities or courses, and kidney donors to recipients, just to mention a few examples. The underlying matching problems have been extensively studied by economists, computer scientists and mathematicians, and many of these researchers also got involved in the design of the allocation mechanisms (a distinguished example is Al Roth, the 2012 Nobel laurate in economics). In this talk we will discuss three applications: the Scottish resident allocation, the Hungarian higher education admissions, and the UK kidney exchange programme (with a quick outlook on the European and French counterparts). Each of these three applications had some special features that made the corresponding problems computationally hard. In the design of the matching algorithms we took an engineering approach, we developed sophisticated heuristics and used integer programming techniques to solve them.