Overview
The Hungarian algorithm finds an optimal one-to-one assignment in a cost matrix by using row/column potentials and augmenting paths in the equality graph.
CoreSource checked
Hungarian Algorithm
Solves the assignment problem by maintaining dual labels and improving a minimum-cost matching.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Optimization
- Difficulty
- Intermediate
- Family
- Assignment Optimization
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 3
- Formulas
- 1
- Relationships
- 6
- Code example
- Ready
- Visualization
- Ready
Core Concepts
assignment problemassignment optimizationdual potentialsmatchingoptimization
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n^2)
Average
O(n^3)
Worst
O(n^3)
Space
O(n^2)
When to Use
- Use when a square or padded rectangular assignment problem needs an exact minimum-cost matching.
- Use when costs are known and each worker/job should be matched at most once.
When Not to Use
- Avoid when assignments have complex side constraints beyond one-to-one matching.
- Avoid when approximate matching is enough and matrix size is too large.
What It Does
- Hungarian Algorithm uses maintaining row and column potentials to find a minimum-cost perfect matching for assignment problem
- Organizes the work around assignment problem and assignment optimization.
Use Cases
- Production and research workloads requiring assignment optimization via using row/column potentials and augmenting paths in the equality graph.
- Assignment Optimization pipelines where O(n^3) time and O(n^2) space fit system constraints.
- Engineering comparisons against Bipartite Matching DFS and Hopcroft-Karp when tuning assignment optimization.
Inputs
- Objective, constraints, and candidate variables
- Problem-specific costs or feasibility rules
Outputs
- Best known feasible solution
- Optimality or approximation result when available
Key Formulas (1)
Reduced assignment cost
reducedcost(i,j) = cost(i,j) − u[i] − v[j]
reduced_cost(i,j) = cost(i,j) - u[i] - v[j]Row and column potentials expose zero-cost assignments.
Pseudocode
- 1.Initialize row and column potentials
- 2.Build the equality graph from tight edges
- 3.Find an augmenting path from an unmatched row
- 4.If blocked, update potentials using minimum slack
- 5.Augment the matching
- 6.Repeat until every row is matched
Canonical Example
- Input
- costs [[4,1],[2,3]] for workers A,B and jobs X,Y
- Output
- assign A->Y and B->X with total cost 3
- Explanation
- The chosen pairing has lower total cost than A->X and B->Y.
Implementation Notes
- Keep row and column potentials separate from the matching.
- Maintain slack values for unmatched columns during augmenting search.
- Test tied optimal assignments and rectangular cases.
Common Pitfalls
- Rectangular matrices need padding or an implementation that handles them directly.
- Maximization problems must be transformed consistently into minimization.
- Floating-point costs require tolerance in equality tests.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow maintaining row and column potentials to find a minimum-cost perfect matching on a small assignment problem example.
Step 1 of 6: Initialize row and column potentials
optimization-mechanismNotes
The algorithm solves a structured bipartite assignment problem, not arbitrary matching with side constraints.
Sources (3)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Hungarian Algorithm's algorithm family, complexity framing, and standard implementation concepts.
Open sourceMatching Theory
BookReference for Hungarian Algorithm's graph matching model and augmenting-path or blossom-style concepts.
Kuhn Hungarian Method
PaperOriginal reference for the Hungarian method for the assignment problem.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toBipartite Matching DFS
Graph Traversal · Core
Both address assignment problem, but they make different modeling or performance tradeoffs.
Compare with thisAlternativesEdmonds' Blossom Algorithm
Graph Traversal · Core
Both address general graph matching, but they make different modeling or performance tradeoffs.
Compare with thisAlternative toHopcroft-Karp
Graph Traversal · Core
Both address assignment problem, but they make different modeling or performance tradeoffs.
Compare with thisRelationships
View full relationship pageAlternative toBipartite Matching DFS
Both address assignment problem, but they make different modeling or performance tradeoffs.
Alternative toHopcroft-Karp
Both address assignment problem, but they make different modeling or performance tradeoffs.
Alternative toMin-Cost Max-Flow
Both address assignment problem, but they make different modeling or performance tradeoffs.
Tags
OptimizationMatching