1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ What, exactly, do you wish the constraint (and objective) to be? $\endgroup$ – Mark L. Stone Jun 8 at 18:33
  • 1
    $\begingroup$ Are you looking to assign multiple jobs to a single person, a single job to multiple people (to be split among them), or both? $\endgroup$ – prubin Jun 8 at 20:23
  • $\begingroup$ I have updated the statement. $\endgroup$ – ephemeral Jun 9 at 3:48
  • $\begingroup$ 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. $\endgroup$ – Mark L. Stone Jun 9 at 11:47
  • 1
    $\begingroup$ 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? $\endgroup$ – Mark L. Stone Jun 9 at 15:01
6
$\begingroup$

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.

I'm an American, so you can call it the American algorithm.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.