The Hungarian Method and its extension

One of the earliest appearances of a special form of the linear programming duality theorem is E. Egerváry's classical result on the maximum weight of a perfect matching in a complete bipartite graph. Its elegant proof gave rise to an efficient algorithm called Hungarian Method. The basic principles of the procedure have been generalized in several directions such as the maximum weight matching problem in nonbipartite graphs, the weighted matroid intersection and the submodular flow problem. In the present work we overview these extensions of the Hungarian Method. As a new contribution, a short proof is given for the weight-splitting version of the weighted matroid intersection theorem.