1
$\begingroup$

I am looking for the general problem class / computational complexity / algorithms for the following problem:

N tasks must be accomplished by N persons. 1 task to be done by exactly 1 person and vice versa. There is a binary preferences matrix whose (i,j) entry is 0 if person i can not do task j, and 1 if it can.

There are no costs involved, no weights and the number of tasks equals the number of people.

I was searching for it but all I could find was the Assignment Problem which has costs/weights associated with each assignment.

As a last resort, perhaps I can transform my preferences matrix to a cost matrix if person can not do job then cost is infinite else cost is zero?

$\endgroup$
  • $\begingroup$ This problem is exactly matching. Refer to Wikipedia for further details. $\endgroup$ – Lwins Jul 5 at 18:43
  • $\begingroup$ you mean "maximum bipartite matching" ( en.wikipedia.org/wiki/Matching_(graph_theory) ). i.e. construct a bipartite graph based on the prefs? Is max-flow the correct direction? $\endgroup$ – bliako Jul 5 at 18:58
1
$\begingroup$

This problem is known as maximum matching of a bipartite graph. Basically let vertex $p_i$ (resp., $q_i$) represent the $i$th person (resp., task). And we connect $p_i$ and $q_j$ with an undirected edge iff person $i$ can do task $j$. The answer of the original problem is exactly the maximum matching of the new graph.

For algorithms, the classical Hungarian algorithm, of complexity $O(n^3)$, is a nice choice. Certainly you can reduce this problem to network flow, and then apply any max-flow algorithm. If you are looking for some "advanced" choices, refer to Wikipedia.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.