Hungarian algorithm
Polynomial-time algorithm for the assignment problem.
The Hungarian algorithm, also known as the Hungarian method, is a combinatorial optimization algorithm that solves the assignment problem in polynomial time. The algorithm anticipated later primal–dual methods and has been reviewed and refined by subsequent researchers.
- field
- Combinatorial optimization
- known_for
- Solving the assignment problem in polynomial time
- developed_by
- Harold Kuhn
- named_after
- Dénes Kőnig and Jenő Egerváry
- also_known_as
- Kuhn–Munkres algorithm or Munkres assignment algorithm
Reader's Guide
The Hungarian algorithm is significant as a foundational method in combinatorial optimization, solving the assignment problem in polynomial time and anticipating later primal–dual methods. Its time complexity was originally O(n⁴), but Edmonds and Karp, and independently Tomizawa, noticed that it can be modified to achieve an O(n³) running time. Ford and Fulkerson extended the method to general maximum flow problems in the form of the Ford–Fulkerson algorithm. The algorithm can be described both in a matrix formulation, where it minimizes the trace of a permuted cost matrix, and in a bipartite graph formulation, where it finds a perfect matching with minimum total cost by maintaining a potential and an orientation of tight edges. Its legacy includes widespread use in operations research and economics for optimal assignment of resources.
Did You Know?
- The algorithm was named 'Hungarian method' by Harold Kuhn because it was largely based on the earlier works of Hungarian mathematicians Dénes Kőnig and Jenő Egerváry.
- Edmonds and Karp, and independently Tomizawa, noticed that the algorithm can be modified to achieve an O(n³) running time.
Frequently Asked Questions
What are Hungarian algorithm's powers/role?
Its signature ability is solving the assignment problem — pairing a set of agents to tasks at minimum total cost — while running in polynomial time instead of brute-force exponential time. In some circles it goes by the alternate names Kuhn–Munkres algorithm or Munkres assignment algorithm.
Why is Hungarian algorithm important?
Before Kuhn's contribution, finding an efficient general solution to the assignment problem was an open challenge, and his method proved a polynomial-time approach was achievable. That result became a cornerstone of combinatorial optimization and showed that structured matching problems could be solved far more efficiently than exhaustive search.
Who named Hungarian algorithm and why?
Harold Kuhn chose the name to honor the Hungarian mathematicians Dénes Kőnig and Jenő Egerváry, whose earlier results on bipartite matching formed the theoretical bedrock of the method. The algorithm is sometimes also called the Kuhn–Munkres algorithm to acknowledge J. Richard Munkres's later refinements of the presentation.
More in Algorithms And Data Structures 25-38
Elsewhere in the Algorithms And Data Structures universe
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record