Computing at Glasgow University
Paper ID: 9112

Finding large stable matchings
Irving,R.W. Manlove,D.F.

Publication Type: Journal
Appeared in: ACM Journal of Experimental Algorithmics, vol 14, section 1, article no. 2
Page Numbers : 1-30
Publisher: ACM
Year: 2009

URL: This publication is available at this URL.


When ties and incomplete preference lists are permitted in the Stable Marriage and Hospitals/Residents problems, stable matchings can have different sizes. The problem of finding a maximum cardinality stable matching in this context is known to be NP-hard, even under very severe restrictions on the number, size and position of ties. In this paper, we present two new heuristics for finding large stable matchings in variants of these problems in which ties are on one side only. We describe an empirical study involving these heuristics and the best existing approximation algorithm for this problem. Our results indicate that all three of these algorithms perform significantly better than naive tie-breaking algorithms when applied to real-world and randomly-generated data sets, and that one of the new heuristics fares slightly better than the other algorithms in most cases. This study, and these particular problem variants, are motivated by important applications in large scale centralized matching schemes.

PDF Bibtex entry Endnote XML