The assignment problem pairs workers with tasks to minimize total cost. In the balanced case, each worker gets one task and the cost matrix is square. section 3.0 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.
A cost matrix places workers in rows and tasks in columns; its values can represent costs or other measurable factors. section 3.1
The Hungarian algorithm improves on checking every possible pairing:
- Subtract each row's minimum, then each column's minimum. section 3.4
- Cover the zeroes with the fewest lines. If fewer than n lines suffice, adjust uncovered and intersecting cells and repeat. section 3.4
- When n lines are needed, select independent zeroes for the assignments and use the original costs to calculate the total. section 3.4
A worker-task match
One solution assigns Alice to Floors, Bob to Kitchen, and Carol to Windows, for a total cost of 27. section 3.1
