Content deleted Content added
→Step 4: make clear that value is uncovered (based on https://medium.com/@riya.tendulkar/the-assignment-problem-using-hungarian-algorithm-4f105729af18) |
→Matrix formulation: removed unnecessary double permutation (due to the cyclic invariance of the trace, the two permutations can be combined into one – only the workers or the jobs need to be permuted, not both) |
||
Line 37:
In the matrix formulation, we are given a nonnegative ''n''×''n'' [[Matrix (mathematics)|matrix]], where the element in the ''i''-th row and ''j''-th column represents the cost of assigning the ''j''-th job to the ''i''-th worker. We have to find an assignment of the jobs to the workers, such that each job is assigned to one worker and each worker is assigned one job, such that the total cost of assignment is minimum.
This can be expressed as permuting the rows
:<math>
\
</math>
where ''
If the goal is to find the assignment that yields the ''maximum'' cost, the problem can be solved by negating the cost matrix ''C''.
| |||