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 [TCS 2020] 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.
Bibtex entry:
AUTHOR | = | {Cs{\'a}ji, Gergely and Kir{\'a}ly, Tam{\'a}s and Yokoi, Yu}, |
TITLE | = | {Solving the Maximum Popular Matching Problem with Matroid Constraints}, |
NOTE | = | {{\tt egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2022}, |
NUMBER | = | {TR-2022-10} |