Access count of this item: 126

Files in This Item:
File Description SizeFormat 
ipsjjip.23.202.pdf449.6 kBAdobe PDFView/Open
Title: Finding Witnesses for Stability in the Hospitals/Residents Problem
Authors: Lee, Minseon
Miyazaki, Shuichi
Iwama, Kazuo
Author's alias: 李, ミンソン
宮崎, 修一
岩間, 一雄
Keywords: the Hospitals/Residents problem
hospital's preference list
NP-complete
first-fit algorithm
Issue Date: 15-Mar-2015
Publisher: Information Processing Society of Japan
Journal title: Journal of Information Processing
Volume: 23
Issue: 2
Start page: 202
End page: 209
Abstract: The Hospitals/Residents problem is a many-to-one generalization of the well-known 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 k-SHPL, in which there are only k kinds of preference lists of hospitals. We show that 1-SHPL is solvable in polynomial time, while k-SHPL is NP-complete 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 (first-fit algorithms) for 2-SHPL. We implement these algorithms and present a computational study using random instances.
Rights: © 2015 by the Information Processing Society of Japan
URI: http://hdl.handle.net/2433/198566
DOI(Published Version): 10.2197/ipsjjip.23.202
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks


Export Format: 


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.