Computing at Glasgow University
Paper ID: 8971
DCS Tech Report Number: TR-2008-287

A 3/2-approximation algorithm for general stable marriage

Publication Type: Tech Report (internal)
Appeared in: DCS Technical Report Series
Page Numbers :
Publisher: Dept of Computing Science, University of Glasgow
Year: 2008

In an instance of the stable marriage problem with ties and incomplete lists, stable matchings can have different sizes. It is NP-hard to compute a maximum cardinality stable matching, and there has been recent interest in finding polynomial time approximation algorithms with a constant performance guarantee for both the general version of this problem, and for several special cases. Our contribution is to describe a 3/2-approximation algorithm, which makes no assumptions about the nature of the ties or preference lists of the instance. The previously best known approximation algorithm for this problem gave a guarantee of 5/3.

Keywords: stable matching; approximation algorithms

PDF Bibtex entry Endnote XML