论文标题
医院/居民问题不完整的列表设置，最大满足较低的配额
Incomplete List Setting of the Hospitals/Residents Problem with Maximally Satisfying Lower Quotas
论文作者
论文摘要
为了减轻医院/居民问题中受让人人数的失衡，Goko等人。 [Goko等人，最大程度地满足医院/居民关系中的较低配额，Proc。 Stacs 2022，第31：1--31：20]研究了医院/居民的问题，其目标是找到稳定的匹配，以尽可能满足较低的配额。在他们的论文中，假定偏好清单是完整的，也就是说，假定每个居民（分别，医院）的偏好清单包含所有医院（分别为居民）。 在本文中，我们研究了一个更通用的模型，其中偏好列表可能不完整。对于四种自然场景，我们获得了最佳和最差解决方案，近似性结果以及不可Ximibibibility的结果的最大差距。
To mitigate the imbalance in the number of assignees in the Hospitals/Residents problem, Goko et al. [Goko et al., Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties, Proc. STACS 2022, pp. 31:1--31:20] studied the Hospitals/Residents problem with lower quotas whose goal is to find a stable matching that satisfies lower quotas as much as possible. In their paper, preference lists are assumed to be complete, that is, the preference list of each resident (resp., hospital) is assumed to contain all the hospitals (resp., residents). In this paper, we study a more general model where preference lists may be incomplete. For four natural scenarios, we obtain maximum gaps of the best and worst solutions, approximability results, and inapproximability results.
