The Hospitals/Residents problem (HR) is a many-to-one matching problem whose solution concept is stability. It is widely used in assignment systems such as assigning medical students (residents) to hospitals. To resolve imbalance in the number of residents assigned to hospitals, an extension called HR with regional caps (HRRC) was introduced. In this problem, a positive integer (called a regional cap) is associated with a subset of hospitals (called a region), and the total number of residents assigned to hospitals in a region must be at most its regional cap. Kamada and Kojima defined strong stability for HRRC and demonstrated that a strongly stable matching does not necessarily exist. Recently, Aziz et al. proved that the problem of determining if a strongly stable matching exists is NP-complete in general. In this paper, we refine Aziz et al.'s result by investigating the computational complexity of the problem in terms of the length of preference lists, the size of regions, and whether or not regions can overlap, and completely classify tractable and intractable cases.
翻译:医院/居民问题(HR)是一个多对一的匹配问题,其解决办法是稳定的,它被广泛用于分配系统,例如将医科学生(居民)分配到医院。为了解决被分配到医院的居民人数的不平衡问题,引入了一个称为区域上限的HR(HRRC)的扩展;在此问题上,一个称为区域上限的正整数(称为区域上限)与一组医院(称为区域)有关,指定到一个区域医院的总人数最多只能是其区域上限。Kamada和Kojima为HR确定了强有力的稳定性,并表明不一定存在一个非常稳定的匹配。最近,Aziz等人证明,确定是否存在一个非常稳定的匹配的问题一般是NP(NP)完成的。在本文件中,我们通过调查在优惠名单长度、区域大小、区域是否能够重叠、以及可完全分类和难易处理的案件等方面对Aziz et al(Aziz et al) 等问题进行计算的复杂性。