Skip to main content
3 of 3
formal description
ephemeral
  • 917
  • 4
  • 12

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?

ephemeral
  • 917
  • 4
  • 12