Is this assignment problem with constrains NP-hard?

Question

It is a many-to-one assignment problem with N tasks and M people.

Each person can get multiple tasks, while each task can be assigned to only one person. We can earn a profit Pij if the task i is assigned to person j.

If T1, T2, ... , Tm is a partition of the tasks, and n1, n2, ..., nm are m positive integers. I want the optimum assignment such that the number of people assigned to any task in Ti must be less or equal to ni

Answer 1

If I understand your question correctly, this is a special case of the minimum-cost flow problem on a graph with three layers (in addition to a source and a sink layer).

• From the source, you have a layer with M vertices, one for each person, connected to the source with edges of capacity 1 and no cost.
• The next layer has the N tasks, and the i'th person is connected to the j'th task with an edge of capacity 1 and cost -P_ij.
• The third layer contains m vertices, one for each part in your partition, and a task is connected to its part with an edge of capacity 1 and no cost.
• Finally, the i'th part is connected to the sink with an edge of capacity n_i and no cost.

We haven't specified a demand, but we could simply try all possible demands between 0 and M and still be in P, so showing that it's not NP-hard is equivalent to showing that P ≠ NP.