|
In 1962 Gale and Shapley gave their famous simple ``proposal'' algorithm, that always finds a stable matching in bipartite graphs. If ties are allowed in the preference lists, we are usually interested not only in finding some stable matching, but one with maximum size. This problem is APX-hard, and probably cannot be approximated within factor 4/3. We first survey the history of approximation algorithms for this problem. McDermid gave the first 3/2-approximation, and very recently Paluch gave a linear time algorithm with the same ratio. In this paper we give a much simpler algorithm, which is only a slight modification of the historical algorithm of Gale and Shapley. This also gives 3/2-approximation in linear time. The proof of the approximation ratio is also uncomplicated, thus it serves as a good example for teaching purposes.
Bibtex entry:
| AUTHOR | = | {Kir{\'a}ly, Zolt{\'a}n}, |
| TITLE | = | {Approximation of Maximum Stable Marriage}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2011}, |
| NUMBER | = | {TR-2011-03} |