Király Tamás: The popular matching problem with matroid constraints

EGERVÁRY SZEMINÁRIUM

Abstract: We consider the problem of finding a maximum popular matching in a many-to-many matching setting with two-sided preferences and matroid constraints. This problem was proposed by Kamiyama and solved in the special case where matroids are base orderable. Utilizing a recently shown matroid exchange property, we show that the problem is tractable for arbitrary matroids.

Joint work with Gergely Csáji and Yu Yokoi.