The Hospitals/Residents Problem with Quota Lower Bounds

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 a

lower

bound 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

ε

where

H

and

R

are 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 time

O

(

t

2

(|

H

|(|

R

| + 

t

))

t

 + 1

) for instances whose optimal cost is

t

. 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

$\sqrt{|R|}$

-approximation algorithm.