hide
Free keywords:
-
Abstract:
We present two $\twothirds - \epsilon$ approximation algorithms for the
maximum weight matching problem that run in time
$O(m\log\frac{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 $\epsilon$ than a recent algorithm by Drake and Hougardy.
We also show that our algorithms can be generalized to find a
$1-\epsilon$ approximatation to the maximum weight matching, for any
$\epsilon>0$.
