# How to allow multiple assignments for jobs in Hungarian Algorithm?

In the Hungarian Algorithm, the assignment for a bipartite graph considers the restriction of assigning a single job to a single person for example. Can this restriction be relaxed? I would like to Minimize the overall cost, while allowing multiple jobs to be assigned to the same person.

We have a bipartite graph $$W = W_1, W_2, \ldots W_n$$ representing workers, and $$J = J_1, J_2, \ldots, J_m$$. We are given an $$m \times n$$ matrix which represents $$C_{i,j}$$, the cost of assigning job $$i$$ to worker $$j$$. Multiple jobs can be assigned to a single worker designated by the cost according to the cost matrix. What would be the minimum cost assignment for such a scenario?

• What, exactly, do you wish the constraint (and objective) to be? Jun 8 '20 at 18:33
• Are you looking to assign multiple jobs to a single person, a single job to multiple people (to be split among them), or both? Jun 8 '20 at 20:23
• I have updated the statement. Jun 9 '20 at 3:48
• Is the cost per job for worker i to do job j the same no matter how many jobs are done by that worker? if so, for each job, just assign the cheapest worker. if there are limits on how many jobs a worker can do, or that cost is not linear in tghe number of jobs a worker does, you need to make that explicit. Jun 9 '20 at 11:47
• Per my previous comment, for each row $i$ (job), assign it to the worker $j$ which minimiizes $C_{i,j}$. I.e., assign the job to the cheapest worker. For this problem the greedy algorithm is simple and optimal. If my algorithm does not optimally solve your problem, what is incorrect about my understanding? Jun 9 '20 at 15:01

For each row, $$i$$ (job), assign it to the worker $$j$$ which minimizes $$C_{i,j}$$. I.e., assign the job to the cheapest worker. For this problem the greedy algorithm is simple and optimal.