Parameterized complexity and local search approaches for the stable marriage problem with ties

Parameterized complexity and local search approaches for the stable marriage problem with ties

0.00 Avg rating0 Votes
Article ID: iaor20104952
Volume: 58
Issue: 1
Start Page Number: 170
End Page Number: 187
Publication Date: Sep 2010
Journal: Algorithmica
Authors: ,
Keywords: graphs
Abstract:

We consider the variant of the classical Stable Marriage problem where preference lists can be incomplete and may contain ties. In such a setting, finding a stable matching of maximum size is NP-hard. We study the parameterized complexity of this problem, where the parameter can be the number of ties, the maximum or the overall length of ties. We also investigate the applicability of a local search algorithm for the problem. Finally, we examine the possibilities for giving an FPT algorithm or an FPT approximation algorithm for finding an egalitarian or a minimum regret matching.

Reviews

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