
Finding Witnesses for Stability in the Hospitals/Residents ProblemFinding Witnesses for Stability in the Hospitals/Residents Problem 
"/Lee, Minseon/"Lee, Minseon ,
"/Miyazaki, Shuichi/"Miyazaki, Shuichi ,
"/Iwama, Kazuo/"Iwama, Kazuo
23
(
2
)
, pp.202

209 , 20150315
ISSN:18826652
Description
The Hospitals/Residents problem is a manytoone generalization of the wellknown Stable Marriage problem. Its instance consists of a set of residents, a set of hospitals, each resident's preference list, each hospital's preference list, and each hospital's capacity (i.e., the number of available positions). It asks to find a stable matching between residents and hospitals. In this paper, we consider the problem of deciding, given residents' preference lists and a matching, whether there are hospitals' preference lists that make a given matching stable. We call this problem Stable Hospital's Preference List problem (SHPL). It is easy to see that there always exists a solution if we allow arbitrary preference lists of hospitals. Considering more suitable situations, we pose a restricted version, called kSHPL, in which there are only k kinds of preference lists of hospitals. We show that 1SHPL is solvable in polynomial time, while kSHPL is NPcomplete for any k such that 2 ≤ k ≤ n1ε, where n is the number of residents and ε is any positive constant. We also present four heuristics algorithms (firstfit algorithms) for 2SHPL. We implement these algorithms and present a computational study using random instances.
FullText
http://repository.kulib.kyotou.ac.jp/dspace/bitstream/2433/198566/1/ipsjjip.23.202.pdf