Is a many to one assignment problem NP-hard?

Question

My apologies if a similar question has been asked. I am solving 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 P_ij if the task i is assigned to person j.

I know that a one-to-one assignment can be solved optimally by Hungarian Algorithm in polynomial time. I think this problem is more difficult than the one-to-one assignment problem, and is also a special case of the generalized assignment problem (GAP), where we have no constraint on the number of tasks a person can be assigned. (Of course, we can put a limit on the number of tasks a person have, but in this case the weight of each task is identical, so it is still a special case of GAP.)

I believe we can attain a sub-optimal solution by applying heuristic approach either with or without the limit on the number of tasks assigned to a person, but is there any algorithm that can solve this problem in polynomial time? Is this problem an NP-hard problem?

Answer 1

The generalized assignment problem is hard because of the differing task sizes. The natural linear program has an integrality gap.

This problem has no such gap and in fact can be formulated as an instance of the minimum-cost circulation problem, solvable in strongly polynomial time. Assuming that the task profits are positive (without loss of generality by adding a constant to all of the potential profits for a task), set up a network with a node for each task, a node for each person, and a source/sink. There is an arc of capacity one from the source/sink to each task, of cost 0. There is an arc of unbounded capacity from each task i to each person j, of cost −P_ij. There is an arc from each person to the source/sink, of capacity equal to the number of tasks that person can do and cost 0.

To get the solution, read off the task to person arcs with flow.