<XML><RECORDS><RECORD><REFERENCE_TYPE>3</REFERENCE_TYPE><REFNUM>8522</REFNUM><AUTHORS><AUTHOR>Irving,R.W.</AUTHOR><AUTHOR>Manlove,D.F.</AUTHOR></AUTHORS><YEAR>2007</YEAR><TITLE>An 8/5 approximation algorithm for a hard variant of stable marriage</TITLE><PLACE_PUBLISHED>Proceedings of COCOON 2007: the 13th Annual International Computing and Combinatorics Conference, volume 4598 of Lecture Notes in Computer Science</PLACE_PUBLISHED><PUBLISHER>Springer</PUBLISHER><PAGES>548-558</PAGES><LABEL>Irving:2007:8522</LABEL><KEYWORDS><KEYWORD>stable matching</KEYWORD></KEYWORDS<ABSTRACT>When ties and incomplete preference lists are permitted in the Stable Marriage problem, stable matchings can have different sizes. The problem of finding a maximum cardinality stable matching in this context is NP-hard, even under very severe restrictions on the number, size and position of ties. In this paper, we describe a polynomial-time 8/5-approximation algorithm for a variant in which ties are on one side only and at the end of the preference lists. This variant is motivated by important applications in large scale centralized matching schemes.</ABSTRACT><URL>http://dx.doi.org/10.1007/978-3-540-73545-8_53</URL></RECORD></RECORDS></XML>