Popular matchings with two-sided preference lists and matroid constraints

摘要

In this paper, we consider the popular matching problem with two-sided preference lists and matroid constraints, which is based on the variants of the popular matching problem proposed by Brandl and Kavitha, and Nasre and Rawat. We prove that there always exists a popular matching in our model, and a popular matching can be found in polynomial time. Furthermore, we prove that if every matroid is weakly base orderable, then we can find a maximum-size popular matching in polynomial time. (C) 2019 Elsevier B.V. All rights reserved.