ダウンロード数: 441
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
1868237.1868239.pdf | 262.65 kB | Adobe PDF | 見る/開く |
タイトル: | Approximation algorithms for the sex-equal stable marriage problem |
著者: | Iwama, Kazuo Miyazaki, Shuichi ![]() ![]() Yanagisawa, Hiroki |
著者名の別形: | 岩間, 一雄 宮崎, 修一 柳澤, 弘揮 |
発行日: | 1-Nov-2010 |
出版者: | Association for Computing Machinery (ACM) |
誌名: | ACM Transactions on Algorithms |
巻: | 7 |
号: | 1 |
論文番号: | 2 |
抄録: | 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. |
著作権等: | © 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, http://doi.acm.org/10.1145/1868237.1868239 This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 |
URI: | http://hdl.handle.net/2433/226949 |
DOI(出版社版): | 10.1145/1868237.1868239 |
出現コレクション: | 学術雑誌掲載論文等 |
![](/dspace/image/articlelinker.gif)
このリポジトリに保管されているアイテムはすべて著作権により保護されています。