Faster and simpler approximation of stable matchings

Katarzyna Paluch

We give a 3/2-approximation algorithm for stable matchings that runs in $O(m)$ time. The previously best known algorithm by McDermid has the same approximation ratio but runs in $O…