Алгоритм решения задачи назначения: от Якоби до Куна-Мункреса

Polynomial time algorithm for the assignment problem
The 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 , however Edmonds and Karp, and independently Tomizawa, noticed that it can be modified to achieve an running time. One of the most popular variants is the Jonker–Volgenant algorithm. Ford and Fulkerson extended the method to general maximum flow problems in form of the Ford–Fulkerson algorithm.

The algorithm can equivalently be described by formulating the problem using a bipartite graph. We have a complete bipartite graph with n worker vertices (S) and n job vertices (T), and the edges (E) each have a nonnegative cost We want to find a perfect matching with a minimum total cost.

We must show that as long as the matching is not of maximum possible size, the algorithm is always able to make progress — that is, to either increase the number of matched edges, or tighten at least one edge. It suffices to show that at least one of the following holds at every step:

M is of maximum possible size. contains an augmenting path. G contains a loose tailed path: a path from some vertex in to a vertex in that consists of any number (possibly zero) of tight edges followed by a single loose edge. The trailing loose edge of a loose tailed path is thus from , guaranteeing that Δ is well defined. If M is of maximum possible size, we are of course finished. Otherwise, by Berge's lemma, there must exist an augmenting path P with respect to M in the underlying graph G. However, this path may not exist in : Although every even numbered edge in P is tight by the definition of M, odd numbered edges may be loose and thus absent from One endpoint of P is in , the other in ; w. l. o. g., suppose it begins in If every edge on P is tight, then it remains an augmenting path in and we are done. Otherwise, let be the first loose edge on P. If then we have found a loose tailed path and we are done. Otherwise, v is reachable from some other path Q of tight edges from a vertex in Let be the subpath of P beginning at v and continuing to the end, and let be the path formed by traveling along Q until a vertex on is reached, and then continuing to the end of Observe that is an augmenting path in G with at least one fewer loose edge than P. P can be replaced with and this reasoning process iterated (formally, using induction on the number of loose edges) until either an augmenting path in or a loose tailed path in G is found.

To show that every edge in M remains after adjusting y, it suffices to show that for an arbitrary edge in M, either both of its endpoints, or neither of them, are in Z. To this end let be an edge in M from T to S. It is easy to see that if v is in Z then u must be too, since every edge in M is tight. Now suppose, toward contradiction, that but u itself cannot be in because it is the endpoint of a matched edge, so there must be some directed path of tight edges from a vertex in to u. This path must avoid v, since that is by assumption not in Z, so the vertex immediately preceding u in this path is some other vertex is a tight edge from T to S and is thus in M. But then M contains two edges that share the vertex u, contradicting the fact that M is a matching. Thus every edge in M has either both endpoints or neither endpoint in Z.

To show that y remains a potential after being adjusted, it suffices to show that no edge has its total potential increased beyond its cost. This is already established for edges in M by the preceding paragraph, so consider an arbitrary edge uv from S to T. If is increased by Δ, then either , in which case is decreased by Δ, leaving the total potential of the edge unchanged, or , in which case the definition of Δ guarantees that Thus y remains a potential.

Suppose there are jobs and workers We describe how to compute for each prefix of jobs the minimum total cost to assign each of these jobs to distinct workers. Specifically, we add the th job and update the total cost in time , yielding an overall time complexity of Note that this is better than when the number of jobs is small relative to the number of workers.

We use the same notation as the previous section, though we modify their definitions as necessary. Let denote the set of the first jobs and denote the set of all workers. Before the th step of the algorithm, we assume that we have a matching on that matches all jobs in and potentials satisfying the following condition: the matching is tight with respect to the potentials, and the potentials of all unmatched workers are zero, and the potentials of all matched workers are non positive. Note that such potentials certify the optimality of the matching. During the th step, we add the th job to to form and initialize At all times, every vertex in will be reachable from the th job in While does not contain a worker that has not been assigned a job, let

and denote any at which the minimum is attained. After adjusting the potentials in the way described in the previous section, there is now a tight edge from to
If is unmatched, then we have an augmenting path in the subgraph of tight edges from to After toggling the matching along this path, we have now matched the first jobs, and this procedure terminates. Otherwise, we add and the job matched with it to
Adjusting potentials takes time. Recomputing and after changing the potentials and also can be done in time. Case 1 can occur at most times before case 2 occurs and the procedure terminates, yielding the overall time complexity of .

This variant of the algorithm follows the formulation given by Flood, and later described more explicitly by Munkres, who proved it runs in time. the minimum number of lines (minimum vertex cover) will be n (the size of maximum matching). Thus, when n lines are required, minimum cost assignment can be found by looking at only zeroes in the matrix.