The Hospitals/Residents Problem with Quota Lower Bounds
The Hospitals/Residents Problem with Quota Lower Bounds
复制标题
DOI：
10.1007/978-3-642-23719-5_16
复制
发表时间：
2011-09
期刊：
影响因子：
--
通讯作者：
Koki Hamada;K. Iwama;S. Miyazaki
中科院分区：
文献类型：
--
作者：
Koki Hamada;K. Iwama;S. Miyazaki
医院/居民问题是稳定婚姻问题的多对一延伸。在其实例中，每家医院都规定了配额，即其提供的职位数量的上限。众所周知，在任何情况下，至少存在一个稳定的匹配，并且找到一个可以在多项式时间内完成。在这篇文章中，我们考虑了一个扩展，其中每个医院不仅指定了一个上界，而且还指定了它的位置数的上界。在这种情况下，可能存在不允许稳定匹配的实例，但是询问是否存在稳定匹配的问题在多项式时间内是可解的。在不存在稳定匹配的情况下，我们考虑寻找一个尽可能稳定的匹配的问题，即具有最少块对的匹配。我们证明了这个问题在(|H| + |R|)1 −ε的比率范围内很难逼近，其中ε分别表示医院集合和居民集合。我们从两个不同的角度来解决这个问题。首先，对于所有上限配额为1的特殊情况，我们给出了一个指数时间精确算法。对于最优代价为1的实例，该算法的运行时间为t2(|H|(|R| +t))t+ 1。其次，我们考虑了优化标准的另一种度量，即参与阻塞对的居民数量。我们证明了这个问题仍然是NP难的，但有一个多项式时间近似算法。
The Hospitals/Residents problem is a many-to-one extension of the stable marriage problem. In its 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 of (|H| + |R|)1 −εfor any positive constantεwhereHandRare the sets of hospitals and residents, respectively. We tackle this hardness from two different angles. First, we give an exponential-time exact algorithm for a special case where all the upper bound quotas are one. This algorithm runs in timeO(t2(|H|(|R| +t))t+ 1) for instances whose optimal cost ist. 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.