Incomplete List Setting of the Hospitals/Residents Problem with Maximally Satisfying Lower Quotas

Autor:	Makino, Kazuhisa, Miyazaki, Shuichi, Yokoi, Yu
Rok vydání:	2022
Předmět:	Computer Science - Computer Science and Game Theory Computer Science - Data Structures and Algorithms 91B68 68Q25
Druh dokumentu:	Working Paper
Popis:	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. Comment: arXiv admin note: text overlap with arXiv:2105.03093
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2203.06660 Zobrazit plný text záznamu View this record from Arxiv