Hungarian algorithm

Imagine you have many jobs to do. You also have many friends to help. Each friend wants a different amount of pay for each job. How can you pick the best way? You want to find the way that costs the least.

One man named Harold Kuhn found a way to do this. He called it the Hungarian method. He named it after two other math experts.

This math helps us match things fairly. It can help us assign workers to tasks. It finds the best plan for everyone. It is a very smart way to solve puzzles.

Imagine you have three workers. One must clean, one must sweep, and one must wash windows. Each worker wants a different amount of pay for each job. How can you pick the best plan? You want to find the way that costs the least amount of money.

Harold Kuhn found a smart way to solve this. He called it the Hungarian method. He named it after two math experts from Hungary. These experts were Dénes Kőnig and Jenő Egerváry. Later, people found that Carl Gustav Jacobi solved this long ago. He did this in the 1800s.

This method uses a grid of numbers. We call this a matrix. The grid shows the cost for every worker and every job. The math helps us find a perfect matching. A perfect matching means every worker gets one job. It also means every job gets one worker. This method is very fast. It helps us solve big puzzles with many people and many tasks.

Imagine you have three workers named Alice, Bob, and Carol. They each need to do one job: cleaning, sweeping, or washing windows. However, each person wants a different amount of pay for each task. Alice might want eight dollars to clean, while Bob only wants five. Finding the best plan is a puzzle. You want to assign exactly one job to each person so the total cost is as low as possible. This is called the assignment problem. The Hungarian method is a clever way to solve this puzzle quickly.

To solve this, mathematicians use a grid of numbers called a matrix. Each row represents a worker, and each column represents a job. The numbers inside the grid show the cost for that specific pair. The method works by looking for a perfect matching. A perfect matching means every worker is paired with exactly one job. The algorithm uses special values called potentials to guide the way. It adjusts these values to find edges that are "tight." A tight edge is a pairing that fits perfectly within the math rules.

This method has a very interesting history. Harold Kuhn published the Hungarian method in 1955. He gave it this name to honor two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry. Their earlier work helped Kuhn build his idea. Later, researchers found that Carl Gustav Jacobi had actually solved this in the 1800s. His solution was published in Latin in 1890, long after he died. Because of these many contributors, some people call it the Kuhn–Munkres algorithm.

Math experts have studied how fast this method works. James Munkres looked at the algorithm in 1957. He noted that it is polynomial, which means it can handle large problems efficiently. Other scientists like Edmonds, Karp, and Tomizawa found ways to make it even faster. They modified the steps to improve the running time. Some versions can solve the problem in $O(n^3)$ time. This makes it very useful for huge sets of data.

Even though it sounds hard, you use these ideas every day. When you share snacks fairly, you are thinking about equal parts. When you organize your toys into groups, you are using patterns. The Hungarian method is just a very advanced way to organize groups. It helps big companies decide how to use their workers or machines. It turns a messy list of costs into a perfect, organized plan. It shows how math can bring order to a complicated world.

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.