Two Algorithms for Maximum and Minimum Weighted Bipartite Matching
Date Issued
2008
Date
2008
Author(s)
Shih, Hung-Pin
Abstract
This thesis applies two algorithms to the maximum and minimum weighted bipartite matching problems. In such matching problems, the maximization and minimization problems are essentially same in that one can be transformednto the other by replacing the weight on each edge with an inverse of the weight. Depending on the algorithms we used, we will choose the maximization or minimization problems for illustrations. We apply the ant colony optimization (ACO) algorithm on a minimum weighted bipartite matchingroblem by transforming the problem to a traveling salesman problem (TSP). It may seem that makes the problem more complicated, but in reality it does not. We call this algorithm “ant-matching,” which can solve any weightedipartite matching problems with or without a perfect matching. Besides, we also apply the Metropolis algorithm to solve the maximum weighted bipartite matching problem. To analyze the performance on these two algorithms, weompare the algorithms with the exact Hungarian algorithm, a well-known combinatorial optimization method for solving the weighted bipartite matching problem.
Subjects
Metropolis algorithm
Ant colony optimization
Maximum weighted bipartite matching
Minimum weighted bipartite matching
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-R95922165-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):3ed400ab60cd89aef702c243e7b08bc6