Hungarian Assignment
Match three workers to three jobs while comparing assignment cost with a dual certificate of optimality.
Free theory articleMatch three workers to three jobs while comparing assignment cost with a dual certificate of optimality.
Concept & interpretation
The Hungarian algorithm solves the minimum-cost bipartite assignment problem by maintaining a feasible dual potential on workers and jobs while augmenting a partial matching along zero reduced-cost edges.
Experiment
Explore how row augmentations and potential updates respond to cost ties in the interactive workspace at https://riano.app/module/hungarian-assignment:
- Keep the default costs and press Step three times to watch each worker augmentation update ui, vj, and the reduced costs rci,j while the final minimum cost remains Pending until row 3 finishes.
- Set the preference cycle matrix [7, 2, 8], [6, 9, 3], [1, 5, 4] and press Finish to verify a minimum cost of 6 and zero duality gap.
- Test boundary ties by setting all entries to 0 or all entries to 9 and confirming that lowest-column tie choices produce 3 assigned pairs with Dual constraints satisfied equal to true.