Paper ID: 8522
An 8/5 approximation algorithm for a hard variant of stable marriage
Proceedings of COCOON 2007: the 13th Annual International Computing and Combinatorics Conference, volume 4598 of Lecture Notes in Computer Science
Page Numbers : 548-558
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