<XML><RECORDS><RECORD><REFERENCE_TYPE>10</REFERENCE_TYPE><REFNUM>8971</REFNUM><AUTHORS><AUTHOR>McDermid,E.</AUTHOR></AUTHORS><YEAR>2008</YEAR><TITLE>A 3/2-approximation algorithm for general stable marriage</TITLE><PLACE_PUBLISHED>DCS Technical Report Series</PLACE_PUBLISHED><PUBLISHER>Dept of Computing Science, University of Glasgow</PUBLISHER><ISBN>TR-2008-287</ISBN><LABEL>McDermid:2008:8971</LABEL><KEYWORDS><KEYWORD>stable matching; approximation algorithms</KEYWORD></KEYWORDS<ABSTRACT>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.</ABSTRACT></RECORD></RECORDS></XML>