Access count of this item: 109

Files in This Item:
File Description SizeFormat 
1868237.1868239.pdf262.65 kBAdobe PDFView/Open
Full metadata record
DC FieldValueLanguage
dc.contributor.authorIwama, Kazuo-
dc.contributor.authorMiyazaki, Shuichi-
dc.contributor.authorYanagisawa, Hiroki-
dc.contributor.alternative岩間, 一雄-
dc.contributor.alternative宮崎, 修一-
dc.contributor.alternative柳澤, 弘揮-
dc.description.abstractThe 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.-
dc.publisherAssociation for Computing Machinery (ACM)-
dc.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,
dc.rightsThis is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。-
dc.titleApproximation algorithms for the sex-equal stable marriage problem-
dc.type.niitypeJournal Article-
dc.identifier.jtitleACM Transactions on Algorithms-
dc.addressKyoto University-
dc.addressKyoto University-
dc.addressIBM Research-
Appears in Collections:Journal Articles

Show simple item record

Export to RefWorks

Export Format: 

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