2026-07-23T15:19:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8393 2024-03-06T10:42:00Z ddc:004 open_access

Popular Matchings with Lower Quotas Nasre, Meghana Nimbhorkar, Prajakta bipartite matchings preferences hospital residents lower-quota popular matchings We consider the well-studied Hospital Residents (HR) problem in the presence of lower quotas (LQ). The input instance consists of a bipartite graph G = (R U H, E) where R and H denote sets of residents and hospitals, respectively. Every vertex has a preference list that imposes a strict ordering on its neighbors. In addition, each hospital has an associated upper-quota and a lower-quota. A matching M in G is an assignment of residents to hospitals, and M is said to be feasible if every resident is assigned to at most one hospital and a hospital is assigned at least its lower-quota many residents and at most its upper-quota many residents. Stability is a de-facto notion of optimality in a model where both sets of vertices have preferences. A matching is stable if no unassigned pair has an incentive to deviate from it. It is well-known that an instance of the HRLQ problem need not admit a feasible stable matching. In this paper, we consider the notion of popularity for the HRLQ problem. A matching M is popular if no other matching M' gets more votes than M when vertices vote between M and M'. When there are no lower quotas, there always exists a stable matching and it is known that every stable matching is popular. We show that in an HRLQ instance, although a feasible stable matching need not exist, there is always a matching that is popular in the set of feasible matchings. We give an efficient algorithm to compute a maximum cardinality matching that is popular amongst all the feasible matchings in an HRLQ instance. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Meghana Nasre and Prajakta Nimbhorkar 2018 Is Part Of LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2017.44 urn:nbn:de:0030-drops-83937 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.44 eng https://creativecommons.org/licenses/by/3.0/legalcode