An optimal assignment pairs workers with distinct tasks so the sum of their measurable costs is as small as possible. A cost matrix records the cost of each possible pairing. section 3.1
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.
Read each row as a worker, each column as a task, and each cell as the cost of that pairing. section 3.1
The Hungarian method works toward a set of non-overlapping zero-cost pairings:
- Subtract each row’s minimum from its entries, then do the same for each column. section 3.1
- Cover all zeros with the fewest horizontal or vertical lines. If the line count equals the matrix size, a one-to-one assignment is possible; otherwise, adjust the matrix using the smallest uncovered value and repeat. section 3.1
Matching people to jobs
For apartment cleaning, Alice is assigned floors for $10, Bob the kitchen for $9, and Carol the windows for $8: $27 total. The same approach can assign developers to software modules using estimated hours as costs. section 3.1
For implementation, SciPy provides `linear_sum_assignment`; the described implementation uses Jonker–Volgenant internally. The method’s stated time complexity is O(n³), which can make larger problems costly. section 3.1 section 3.3
