Hungarian algorithm

The Hungarian method is a combinatorial optimization algorithm. It is used to solve a specific puzzle known as the assignment problem. This problem asks for the most efficient way to pair a set of items with another set. For example, you might need to assign several workers to several different tasks. Each worker has a different cost for each task. The goal is to find a way to give every worker exactly one job so that the total cost is as low as possible. This algorithm is highly efficient because it solves the problem in polynomial time.

To understand how the algorithm works, we can look at it through a matrix. In a matrix formulation, we use an $n \times n$ grid of numbers. Each row represents a worker, and each column represents a job. The number at a specific row and column shows the cost of that worker doing that job. Mathematically, the goal is to permute the rows of this cost matrix to minimize the trace of the matrix. If you wanted to find the maximum cost instead of the minimum, you could simply negate the values in the matrix.

Another way to view this is through a bipartite graph. A bipartite graph is a network where two different groups of points, or vertices, are connected. In this case, one group of vertices represents the workers, and the other represents the jobs. The lines connecting them, called edges, each have a cost. The algorithm seeks a perfect matching with the minimum total cost. A perfect matching means every single vertex is paired with exactly one edge.

The algorithm relies on a concept called a potential. A potential is a value assigned to each vertex in the graph. The sum of these potentials provides a baseline for the total cost. The Hungarian method works by finding a perfect matching using only "tight" edges. An edge is considered tight if its cost is equal to the sum of the potentials of its two endpoints. During the process, the algorithm maintains a set of these tight edges and adjusts the potentials to find more of them.

The history of this method involves several important mathematicians. Harold Kuhn published the algorithm in 1955. He named it the "Hungarian method" to honor the work of Dénes Kőnig and Jenő Egerváry. However, researchers discovered in 2006 that Carl Gustav Jacobi had solved this problem much earlier. His solution was published in 1890 in Latin, appearing after his death. Because of these various contributors, the method is also called the Kuhn–Munkres algorithm.

Efficiency is a major part of why this algorithm is so important. In 1957, James Munkres observed that the algorithm is strongly polynomial. This means it can handle large amounts of data without taking an impossible amount of time. Later, scientists like Edmonds, Karp, and Tomizawa found ways to modify the algorithm to improve its running time. Some advanced versions can complete the task in $O(n^3)$ time. This speed makes it possible to solve very large assignment problems that would be impossible to do by hand.

The Hungarian method connects to many different areas of mathematics and science. It is closely related to the study of maximum flow problems. In fact, Ford and Fulkerson extended these ideas to create the Ford–Fulkerson algorithm. By understanding how to move "flow" through a network, scientists can solve even more complex versions of the assignment problem. This makes the Hungarian method a foundational tool in the field of optimization.