Computing at Glasgow University
Paper ID: 8522

An 8/5 approximation algorithm for a hard variant of stable marriage
Irving,R.W. Manlove,D.F.

Publication Type: Conference Proceedings
Appeared in: Proceedings of COCOON 2007: the 13th Annual International Computing and Combinatorics Conference, volume 4598 of Lecture Notes in Computer Science
Page Numbers : 548-558
Publisher: Springer
Year: 2007

URL: This publication is available at this URL.


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.

Keywords: stable matching, approximation algorithm

PDF Bibtex entry Endnote XML