The Hungarian algorithm or Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal–dual methods. It was developed and published in 1955 by Harold Kuhn, who gave it the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry. However, in 2006 it was discovered that Carl Gustav Jacobi had solved the assignment problem in the 19th century, and the solution had been published posthumously in 1890 in Latin. James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial. Since then the algorithm has been known also as the Kuhn–Munkres algorithm or Munkres assignment algorithm. The time complexity of the original algorithm was O ( n 4 ) {\displaystyle O(n^{4})} , however Edmonds and Karp, and independently Tomizawa, noticed that it can be modified to achieve an O ( n 3 ) {\displaystyle O(n^{3})} running time. Ford and Fulkerson extended the method to general maximum flow problems in the form of the Ford–Fulkerson algorithm.
The problem
Example In this simple example, there are three workers: Alice, Bob and Carol. One of them has to clean the bathroom, another sweep the floors and the third washes the windows, but they each demand different pay for the various tasks. The problem is to find the lowest-cost way to assign the jobs. The problem can be represented in a matrix of the costs of the workers doing the jobs. For example:
The Hungarian method, when applied to the above table, would give the minimum cost: this is $15, achieved by having Alice clean the bathroom, Carol sweep the floors, and Bob wash the windows. This can be confirmed using brute force:
(the unassigned person washes the windows)
Matrix formulation In the matrix formulation, we are given an n×n matrix, where the element in the i-th row and j-th column represents the cost of assigning the j-th job to the i-th worker. We have to find an assignment of the jobs to the workers, such that each job is assigned to one worker and each worker is assigned one job, such that the total cost of assignment is minimum. This can be expressed as permuting the rows of a cost matrix C to minimize the trace of a matrix,
min P Tr ( P C ) , {\displaystyle \min _{P}\operatorname {Tr} (PC)\;,}
where P is a permutation matrix. (Equivalently, the columns can be permuted using CP.) If the goal is to find the assignment that yields the maximum cost, the problem can be solved by negating the cost matrix C.
Bipartite graph formulation The algorithm can equivalently be described by formulating the problem using a bipartite graph. We have a complete bipartite graph G = ( S , T ; E ) {\displaystyle G=(S,T;E)} with n worker vertices (S) and n job vertices (T), and the edges (E) each have a cost c ( i , j ) {\displaystyle c(i,j)} . We want to find a perfect matching with a minimum total cost.
The algorithm in terms of bipartite graphs Let us call a function y : ( S ∪ T ) → R {\displaystyle y:(S\cup T)\to \mathbb {R} } a potential if y ( i ) + y ( j ) ≤ c ( i , j ) {\displaystyle y(i)+y(j)\leq c(i,j)} for each i ∈ S , j ∈ T {\displaystyle i\in S,j\in T} . The value of potential y is the sum of the potential over all vertices:
… excerpt ends here. Continue reading the full article.
