论文标题
关于稳定的多一对一匹配问题，具有下部和上部配额的稳定匹配问题
A Fine-Grained View on Stable Many-To-One Matching Problems with Lower and Upper Quotas
论文作者
论文摘要
在医院居民的问题中，上等配额（$ hr-q^u_l $），目标是找到稳定的居民与医院的匹配，在这些医院中，与医院相匹配的居民的数量在其下部和零之间或零之间或零[Biró等人[Biró等人，TCS 2010]]。我们使用几个自然参数（例如医院数量和居民数量）从参数化的角度分析了这个问题。此外，我们提出了一种多项式时间算法，如果在最大较低的配额二的实例上存在稳定的匹配，则可以找到稳定的匹配。除$ hr-q^u_l $之外，我们还考虑了两种密切相关的独立兴趣模型，即，$ hr-q^u_l $的特殊情况，其中每家医院只有一个较低的配额，但没有上限和$ hr-q^u_l $的变化，而医院与居民没有偏好的偏好，而居住的房屋则是较低的山顶，并没有偏好。最后，我们研究了这三个模型的参数化复杂性如果偏好可能包含纽带，如何改变。
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ó 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.
