A simpler linear time 2/3-epsilon approximation for maximum weight matching
We present two 2/3 - epsilon approximation algorithms for the maximum weight matching problem that run in time O(m log 1/epsilon We give a simple and practical randomized algorithm and a somewhat more complicated deterministic algorithm. Both algorithms are exponentially faster in terms of s than a recent algorithm by Drake and Hougardy. We also show that our algorithms can be generalized to find a 1 - epsilon approximation to the maximum weight matching, for any epsilon > 0. (C) 2004 Elsevier B.V. All rights reserved.
approximation maximum weight matching matching analysis of algorithms