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. It was developed and published in 1955 by Harold Kuhn, who named it after the Hungarian mathematicians Dénes Kőnig and Jenő Egerváry, as their earlier work formed its foundation. However, it was later discovered in 2006 that Carl Gustav Jacobi had solved the assignment problem in the 19th century, with his solution published posthumously in 1890 in Latin. In 1957, James Munkres reviewed the algorithm and noted that it is strongly polynomial; consequently, it is also referred to as the Kuhn–Munkres algorithm or Munkres assignment algorithm. The original algorithm had a specific time complexity, but Edmonds and Karp, along with Tomizawa independently, found that it could be modified to achieve a different running time. Ford and Fulkerson extended the method to general maximum flow problems, leading to the Ford–Fulkerson algorithm. The algorithm can be formulated using a cost matrix, where the goal is to find a permutation that minimizes the trace, or equivalently using a bipartite graph with worker and job vertices, seeking a perfect matching of minimum total cost. The method works by maintaining a potential function and a subgraph of tight edges, iteratively adjusting the potential or the orientation of edges to increase the matching size until a perfect matching is found, which guarantees optimality.
- 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
Lore & Background
The Hungarian algorithm is a combinatorial optimization method designed to solve the assignment problem in polynomial time, and it is recognized as a forerunner of later primal–dual techniques. Harold Kuhn developed and published the algorithm in 1955, naming it the "Hungarian method" because it drew heavily on prior work by Hungarian mathematicians Dénes Kőnig and Jenő Egerváry. A later discovery in 2006 revealed that Carl Gustav Jacobi had already solved the assignment problem in the 19th century, with his solution appearing posthumously in 1890 in Latin. James Munkres reviewed the algorithm in 1957 and noted its strongly polynomial nature; since then, it has also been called the Kuhn–Munkres algorithm or Munkres assignment algorithm. The original algorithm had a specific time complexity, but Edmonds and Karp, as well as Tomizawa independently, found that modifications could achieve an improved running time. Ford and Fulkerson extended the method to general maximum flow problems through the Ford–Fulkerson algorithm. The algorithm can be formulated using a cost matrix, where the goal is to permute rows to minimize the trace of the matrix, or equivalently via a bipartite graph with worker and job vertices, seeking a perfect matching of minimum total cost. It operates by maintaining a potential function and an orientation of tight edges, iteratively adjusting the potential or the orientation to increase the matching size until a perfect matching is found, which guarantees an optimal assignment.
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 1-24
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