The Hungarian algorithm finds a minimum-cost one-to-one assignment, such as matching workers to tasks. It uses a square cost matrix: rows represent workers, columns represent tasks, and each cell records a pairing’s cost. section 3.0 section 3.1
The core procedure turns the assignment into a sequence of manageable checks:
- Subtract each row’s minimum from every value in that row, then do the same for each column. section 3.1
- Cover every zero with the fewest horizontal or vertical lines. If the number of lines equals the matrix size, select independent zeroes for the assignments. section 3.1 section 3.4
- If fewer lines are needed, subtract the smallest uncovered value from uncovered cells and add it at line intersections; repeat the check. section 3.4
Matching cleaners to rooms
For three cleaners and three rooms, the resulting assignment gives Bob the kitchen, Carol the windows, and Alice the floors, for a total cost of $27. section 3.1
Trying every permutation takes factorial time; the Hungarian algorithm reduces the work to O(n³). It is useful for one-to-one matching, though production settings may require variations when the numbers of workers and tasks differ. section 3.0 section 3.2
Figure 3.1 Cost matrix is created with the rows representing the workers and the columns representing the tasks. The values in the matrix denote the cost to complete the task. The cost can be replaced by other factors based on the use case like time taken, amount of work, or any other measurable value.
Use the cost-matrix figure to see how workers, tasks, and pairing costs map to rows, columns, and cells. section 3.1
