Min-Cost Popular Matchings in a Hospitals/Residents Instance with Complete Preferences

• 成果类型: Article; Early Access
• 署名作者: Kavitha, Telikepalli; Makino, Kazuhisa
• 署名单位: Tata Institute of Fundamental Research (TIFR); Tata Institute of Fundamental Research (TIFR), Mumbai; Kyoto University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2024.0634
• 发表日期: 2025-11-25
• 关键词: Popular matching; b-matching; stable matching; stable matchings; STABILITY; admissions

摘要

We consider a matching problem in a hospitals/residents instance G, that is, a many-to-one matching instance, in which every vertex has a strict ranking of its neighbors and hospitals have capacities. A matching M is said to be popular if M does not lose an election against any matching in which vertices cast votes for one matching versus another. There are efficient algorithms to find popular matchings in G, but it is NP-hard to find a min-cost popular matching when edges have costs. When preferences are complete, there is a polynomial-time algorithm for this problem in the one-to-one setting. Interestingly, the set of popular matchings in a many-to-one instance can be richer than the set of popular matchings in the corresponding one-to-one instance obtained by cloning vertices. No polynomial-time algorithm is currently known for the min-cost popular matching problem with complete preferences in the many-to-one setting. We show a polynomial-time algorithm for this problem. Our algorithm includes a subroutine for computing a min-cost popular perfect matching; this subroutine also works for instances with incomplete preferences.