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
