The Hospitals/Residents Problem with Lower Quotas
The Hospitals/Residents Problem with Lower Quotas
复制标题
DOI：
10.1007/s00453-014-9951-z
复制
发表时间：
2014-10
期刊：
影响因子：
1.1
通讯作者：
Koki Hamada;K. Iwama;S. Miyazaki
中科院分区：
文献类型：
--
作者：
Koki Hamada;K. Iwama;S. Miyazaki
医院/住院医生问题是稳定婚姻问题的多对一延伸。在一个实例中，每个医院指定一个配额，即它提供的职位数量的上限。众所周知，在任何情况下，至少存在一个稳定的匹配，而找到一个稳定的匹配可以在多项式时间内完成。在本文中，我们考虑一个扩展，其中每个医院不仅有其位置数目的上界，而且有其位置数目的下界。在这种情况下，可能存在不允许稳定匹配的实例，但是询问是否存在稳定匹配的问题可以在多项式时间内解决。在没有稳定匹配的情况下，我们考虑寻找一个“尽可能稳定”的匹配问题，即具有最小数量的阻塞对的匹配。我们证明了这个问题很难在任何正常数的比率内近似，分别是医院和居民的集合。然后我们从两个不同的角度来解决这个难题。首先，给出了一个指数时间精确算法，其运行时间为，其中为最优解中的阻塞对数。其次，我们考虑了优化标准的另一个度量，即参与阻塞对的居民数量。我们证明了这个问题仍然是np困难的，但有一个多项式时间逼近算法。
The Hospitals/Residents problem is a many-to-one extension of the stable marriage problem. In an instance, each hospital specifies a quota, i.e., an upper bound on the number of positions it provides. It is well-known that in any instance, there exists at least one stable matching, and finding one can be done in polynomial time. In this paper, we consider an extension in which each hospital specifies not only an upper bound but also alowerbound on its number of positions. In this setting, there can be instances that admit no stable matching, but the problem of asking if there is a stable matching is solvable in polynomial time. In case there is no stable matching, we consider the problem of finding a matching that is “as stable as possible”, namely, a matching with a minimum number of blocking pairs. We show that this problem is hard to approximate within the ratio offor any positive constantwhereandare the sets of hospitals and residents, respectively. We then tackle this hardness from two different angles. First, we give an exponential-time exact algorithm whose running time is, whereis the number of blocking pairs in an optimal solution. Second, we consider another measure for optimization criteria, i.e., the number of residents who are involved in blocking pairs. We show that this problem is still NP-hard but has a polynomial-time-approximation algorithm.