Stable assignment with couples: Parameterized complexity and local search

Stable assignment with couples: Parameterized complexity and local search

0.00 Avg rating0 Votes
Article ID: iaor20112716
Volume: 8
Issue: 1
Start Page Number: 25
End Page Number: 40
Publication Date: Feb 2011
Journal: Discrete Optimization
Authors: ,
Keywords: heuristics: local search, programming: assignment
Abstract:

We study the Hospitals/Residents with Couples problem, a variant of the classical Stable Marriage problem. This is the extension of the Hospitals/Residents problem where residents are allowed to form pairs and submit joint rankings over hospitals. We use the framework of parameterized complexity, considering the number of couples as a parameter. We also apply a local search approach, and examine the possibilities for giving FPT algorithms applicable in this context. Furthermore, we also investigate the matching problem containing couples that is the simplified version of the Hospitals/Residents with Couples problem modeling the case when no preferences are given.

Reviews

Required fields are marked *. Your email address will not be published.