← Gallery

About

The Hungarian Algorithm (Kuhn 1955, Munkres 1957) finds a maximum-weight perfect matching in a bipartite graph. Unlike Gale-Shapley which optimizes stability with ordinal preferences, Hungarian optimizes total social welfare with cardinal utilities.

Algorithm Steps 
1. ROW REDUCTION: Subtract the
   minimum of each row from all
   elements in that row

2. COLUMN REDUCTION: Subtract the
   minimum of each column from all
   elements in that column

3. COVER ZEROS: Find minimum number
   of lines (rows/cols) to cover
   all zeros

4. CHECK: If #lines = n, optimal
   assignment exists among zeros.
   Done!

5. UPDATE: Find minimum uncovered
   value. Subtract from uncovered
   elements, add to doubly-covered.
   Go to step 3.

Time complexity: O(n^3)

Controls

Click any cell in the matrix to edit values, then run the algorithm.

Properties

Finds globally optimal (max total utility) assignment
Time complexity: O(n^3)
Works with cardinal utilities (not just ordinal rankings)
For n=4: at most 64 operations

Hungarian vs Gale-Shapley

Gale-Shapley optimizes STABILITY (no blocking pairs) using ordinal preferences.

Hungarian Algorithm optimizes TOTAL WELFARE (maximum social utility) using cardinal values.

These are fundamentally different objectives. A stable matching may not maximize total welfare, and a welfare-maximizing matching may not be stable.

Applications:
- Job/task assignment in operations research
- Logistics and transportation optimization
- Computer vision (feature point matching)
- Resource allocation in cloud computing
- Organ donor matching (with modifications)

Event Log

Hungarian Algorithm

Kuhn (1955) / Munkres (1957) — Maximum Weight Perfect Matching in O(n^3)

Utility Matrix (click cells to edit)