Hungarian Assignment

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.

Primal-Dual Concept

Given a 3x3 nonnegative integer cost matrix C_i,j, we seek a bijection pairing each worker i in {1, 2, 3} to a distinct job j in {1, 2, 3} that minimizes the sum of assigned edge costs. Rather than searching all 3! = 6 permutations by brute force, the Hungarian method processes rows sequentially and maintains dual potentials u_i and v_j.

Linear Programming Duality and Reduced Costs

Every valid state satisfies the dual feasibility condition u_i + v_j ≤ C_i,j for all row-column pairs (i, j), defining a nonnegative reduced cost rc_i,j = C_i,j - u_i - v_j ≥ 0. Complementary slackness guarantees that if a complete matching uses only tight edges with rc_i,j = 0, then the primal assignment cost equals the dual potential sum u₁ + u₂ + u₃ + v₁ + v₂ + v₃, proving global optimality with a duality gap of 0.

Worked Example

Consider the default 3x3 cost matrix with rows [4, 1, 3], [2, 0, 5], and [3, 2, 2]:

Row 1: 4  1  3\n Row 2: 2  0  5\n Row 3: 3  2  2

Augment Row 1: Minimum entry in row 1 is C_1,2 = 1 at column 2. Raise u₁ to 1 and match worker 1 to job 2.
Augment Row 2: Entry C_2,2 = 0 has reduced cost 0 - 0 - 0 = 0, which ties column 2. Augmenting along the shortest reduced-cost path updates potentials and matches worker 2 to job 2 (or re-routes worker 1 to job 2 and worker 2 to job 1) with tight dual constraints.
Augment Row 3: Worker 3 is augmented into the remaining tight column. At completion, the optimal assignment pairs (r1, c2) = 1, (r2, c1) = 2, and (r3, c3) = 2 for a minimum total cost of 1 + 2 + 2 = 5 and duality gap 0.

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 u_i, v_j, and the reduced costs rc_i,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.

Limitations

This module models a balanced 3x3 assignment problem with integer edge weights in [0, 9] and a minimization objective. Rectangular or incomplete bipartite graphs require dummy rows/columns or large sentinel costs, and multiple optimal matchings may exist when zero reduced-cost cycles occur.

Common Pitfalls

A frequent mistake is reporting the sum of a partial matching after 1 or 2 steps as a valid lower bound on the final cost. Because later augmentations can reassign previously matched columns and raise dual potentials, the minimum cost is only defined once all three workers are matched.

References

The potential-based O(n³) primal-dual formulation implemented in this module follows standard combinatorial optimization references:

CP-Algorithms: Hungarian Algorithm for the Assignment Problem

Hungarian Assignment