Improved Linear Time Approximation Algorithms for Weighted Matchings

摘要

The weighted matching problem is to find a matching in a weighted graph that has maximum weight. The fastest known algorithm for this problem has running time O(nm + n~2 log n). Many real world problems require graphs of such large size that this running time is too costly. We present a linear time approximation algorithm for the weighted matching problem with a performance ratio of 2/3 - ε.