IISc-CSA-TR-2009-3
(March 2009)

Available formats: (none)

Filed on March 18, 2009
Updated on April 2, 2009


We consider the problem of matching people to jobs, where each person ranks a
subset of jobs in an order of preference, possibly involving ties.
There are several notions of optimality about how to
best match each person to a job; in particular, popularity is a natural
and appealing notion of optimality.
However, popular matchings do not always provide an answer to the problem of
determining an optimal matching since there are simple instances that do not
admit popular matchings.
This motivates the following extension of the popular matchings problem:

Given a graph G = (A U J, E) where A is the set of people and J is the set of
jobs, and a list {c_1, c_2, ..., c_|J|} denoting upper bounds on the
capacities of each job, does there exist (x_1, x_2, ...,x_|J|) such that for
each i, setting the capacity of i-th job to x_i, where 1 <= x_i <= c_i,
enables the resulting graph to admit a popular matching.

In this paper we show that the above problem is NP-hard. We show that the
problem is NP-hard even when each c_i is 1 or 2. We also show a polynomial time
algorithm for a variant of this problem.


Please bookmark this technical report as http://aditya.csa.iisc.ernet.in/TR/2009/3/.

Problems ? Contact techrep@csa.iisc.ernet.in
[Updated at 2009-10-22T06:42Z]