Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems

Robert W. Irving () and David F. Manlove ()
Additional contact information
Robert W. Irving: University of Glasgow
David F. Manlove: University of Glasgow

Journal of Combinatorial Optimization, 2008, vol. 16, issue 3, No 6, 279-292

Abstract: Abstract 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 matching; Weak stability; NP-hard problems; Approximation algorithms (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-007-9133-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:16:y:2008:i:3:d:10.1007_s10878-007-9133-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-007-9133-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().