A Fine-Grained View on Stable Many-To-One Matching Problems with Lower and Upper Quotas
| Autor: | Niclas Boehmer, Klaus Heeger |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Marketing Statistics and Probability Computational Mathematics Economics and Econometrics Discrete Mathematics (cs.DM) Computer Science - Computer Science and Game Theory Computer Science (miscellaneous) Computer Science and Game Theory (cs.GT) Computer Science - Discrete Mathematics |
| Popis: | In the Hospital Residents problem with lower and upper quotas ($HR-Q^U_L$), the goal is to find a stable matching of residents to hospitals where the number of residents matched to a hospital is either between its lower and upper quota or zero [Bir\'o et al., TCS 2010]. We analyze this problem from a parameterized perspective using several natural parameters such as the number of hospitals and the number of residents. Moreover, we present a polynomial-time algorithm that finds a stable matching if it exists on instances with maximum lower quota two. Alongside $HR-Q^U_L$, we also consider two closely related models of independent interest, namely, the special case of $HR-Q^U_L$ where each hospital has only a lower quota but no upper quota and the variation of $HR-Q^U_L$ where hospitals do not have preferences over residents, which is also known as the House Allocation problem with lower and upper quotas. Lastly, we investigate how the parameterized complexity of these three models changes if preferences may contain ties. Comment: Accepted to WINE 2020 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|