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?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ What, exactly, do you wish the constraint (and objective) to be? $\endgroup$
    – Mark L. Stone
    Commented Jun 8, 2020 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 ♦
    Commented Jun 8, 2020 at 20:23
  • $\begingroup$ I have updated the statement. $\endgroup$
    – ephemeral
    Commented Jun 9, 2020 at 3:48
  • 1
    $\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
    Commented Jun 9, 2020 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
    Commented Jun 9, 2020 at 15:01

1 Answer 1

Reset to default
8
$\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 and acknowledge you have read our privacy policy.

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