Weighted bipartite matching and the Hungarian method

Abstract

The Assignment Problem, a major problem in combinatorial optimization, can be related to graph theory as finding an optimal weight matching in a weighted bipartite graph. We have considered the Hungarian algorithm which was found by Harold W. Kuhn in 1955. The algorithm is to find a maximum (minimum) weight perfect matching, in polynomial time. It replaces the original graph with a weighted covering and converts the problem into finding a weighted covering with a perfect matching. Starting with an arbitrary matching, it progresses in iterations such that in the iteration to find a matching of size with maximum weight. This is a better way to solve the assignment problem; Sometimes there may be a better solution than the algorithm returns. Because the algorithm always returns a perfect matching, but a graph with large number of vertices, one can neglect some edges with small weights to obtain a better maximum weight matching without the perfectivenes