Leírás
EGERVÁRY SZEMINÁRIUM
Abstract: We consider many-to-one matching problems, where one side
consists of students and the other side of schools with capacity
constraints. We study how to optimally increase the capacities of the
schools so as to obtain a stable and perfect matching (i.e., every
student is matched) or a matching that is stable and Pareto-efficient
for the students. We consider two common optimality criteria, one
aiming to minimize the sum of capacity increases of all schools
(abbrv. as MinSum) and the other aiming to minimize the maximum
capacity increase of any school (abbrv. as MinMax). We obtain a
complete picture in terms of computational complexity: Except for
stable and perfect matchings using the MinMax criteria which is
polynomial-time solvable, all three remaining problems are NP-hard. We
further investigate the parameterized complexity and approximability
and find that achieving stable and Pareto-efficient matchings via
minimal capacity increases is much harder than achieving stable and
perfect matchings. Joint work with Jiehua Chen.