Access count of this item: 48

Files in This Item:
File Description SizeFormat 
LIPIcs-ISAAC-2017-56.pdf488.66 kBAdobe PDFView/Open
Title: Jointly stable matchings
Authors: Miyazaki, Shuichi
Okamoto, Kazuya
Author's alias: 宮崎, 修一
岡本, 和也
Keywords: stable marriage problem
stable matching
NP-completeness
linear time algorithm
Issue Date: 2017
Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Journal title: Leibniz International Proceedings in Informatics, LIPIcs
Volume: 92
Start page: 56:1
End page: 56:12
Abstract: In the stable marriage problem, we are given a set of men, a set of women, and each person's preference list. Our task is to find a stable matching, that is, a matching admitting no unmatched (man, woman)-pair each of which improves the situation by being matched together. It is known that any instance admits at least one stable matching. In this paper, we consider a natural extension where k (>= 2) sets of preference lists L_i (1 <= i <= k) over the same set of people are given, and the aim is to find a jointly stable matching, a matching that is stable with respect to all L_i. We show that the decision problem is NP-complete already for k=2, even if each person's preference list is of length at most four, while it is solvable in linear time for any k if each man's preference list is of length at most two (women's lists can be of unbounded length). We also show that if each woman's preference lists are same in all L_i, then the problem can be solved in linear time.
Description: 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Rights: © Shuichi Miyazaki and Kazuya Okamoto; licensed under Creative Commons License CC-BY
URI: http://hdl.handle.net/2433/234947
DOI(Published Version): 10.4230/LIPIcs.ISAAC.2017.56
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks


Export Format: 


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.