Hungarian algorithm: multiple jobs per worker

Approach 1

One simple way of doing this is to make, for example, 50 clones of each worker and solve the problem as normal.

To find worker 1's jobs, you can then collect all the jobs assigned to the clones of worker 1. There are only 50 clones, so worker 1 will be assigned to at most 50 jobs.

Approach 2

This kind of assignment problem can be expressed as a min-cost flow problem where there is flow from a worker to a job if the worker does a job.

In this formulation, each worker is supplied with a capacity of 1 flow unit. You can then increase the number of jobs by simply increasing the capacity as required.

This approach is likely to be more efficient (as the graph is smaller) but requires modification of the underlying algorithm, whereas approach 1 should be trivial to implement.

This can be solved by formulating it as a transportation problem with the workers having bounds of [50,inf). Correct me if I am wrong, approach 1 from peter's solution is for when a person can do a maximum of 50, not minimum.