Access count of this item: 102

Files in This Item:
File Description SizeFormat 
1868237.1868239.pdf262.65 kBAdobe PDFView/Open
Title: Approximation algorithms for the sex-equal stable marriage problem
Authors: Iwama, Kazuo
Miyazaki, Shuichi  kyouindb  KAKEN_id
Yanagisawa, Hiroki
Author's alias: 岩間, 一雄
宮崎, 修一
柳澤, 弘揮
Issue Date: 1-Nov-2010
Publisher: Association for Computing Machinery (ACM)
Journal title: ACM Transactions on Algorithms
Volume: 7
Issue: 1
Thesis number: 2
Abstract: The stable marriage problem is a classical matching problem introduced by Gale and Shapley. It is known that for any instance, there exists a solution, and there is a polynomial time algorithm to find one. However, the matching obtained by this algorithm is man-optimal, that is, the matching is favorable for men but unfavorable for women, (or, if we exchange the roles of men and women, the resulting matching is woman-optimal). The sex-equal stable marriage problem, posed by Gusfield and Irving, seeks a stable matching “fair” for both genders. Specifically it seeks a stable matching with the property that the sum of the men's scores is as close as possible to that of the women's. This problem is known to be strongly NP-hard. In this paper, we give a polynomial time algorithm for finding a near optimal solution for the sex-equal stable marriage problem. Furthermore, we consider the problem of optimizing an additional criterion: among stable matchings that are near optimal in terms of the sex-equality, find a minimum egalitarian stable matching. We show that this problem is strongly NP-hard, and give a polynomial time algorithm whose approximation ratio is less than two.
Rights: © ACM, 2010. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in 'ACM Transactions on Algorithms' Volume 7 Issue 1, November 2010,
This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。
DOI(Published Version): 10.1145/1868237.1868239
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.