Computing at Glasgow University
Paper ID: 8713
DCS Tech Report Number: TR-2007-258

Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
Irving,R.W. Manlove,D.F.

Publication Type: Tech Report (internal)
Appeared in: DCS Technical Report Series
Page Numbers :
Publisher: Dept of Computing Science, University of Glasgow
Year: 2007

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 describe polynomial-time 5/3-approximation algorithms for variants of these problems in which ties are on one side only and at the end of the preference lists. The particular variant is motivated by important applications in large scale centralised matching schemes.

Keywords: Stable marriage problem; Hospitals / Residents problem; ties; NP-hardness; approximation algorithm

PDF Bibtex entry Endnote XML