| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2008-03-10 09:30 男女平等安定マッチング問題に対する近似アルゴリズム ○柳澤弘揮（日本IBM）・宮崎修一・岩間一雄（京大）  COMP2007-55 |
|
| 抄録 | （和） | 安定結婚問題は，Gale と Shapley によって提案されたマッチングの問題である．任意の例題について，解が存在し，それを見つける多項式時間が存在することが知られている．しかし，このアルゴリズムによって得られるマッチングは「男性最適」，つまり，男性にとっては好ましいが女性にとっては好ましくないマッチングである（逆に，男女の役割を入れ替えれば，女性最適なマッチングになる）．Gusfield と Irving によって提案された男女平等安定マッチング問題は，男女両者にとって「公平な」安定マッチングを求める，つまり，男性側の不満足度の和が女性側の不満足度の和になるべく近づくような安定マッチングを求める問題である．この問題は，強 NP 困難であることが知られている． 本稿では，男女平等安定マッチング問題に対して，ほぼ最適な解を求める多項式時間アルゴリズムを与える．さらに，評価指標を一つ増やして，男女平等（sex-equality）の観点でほぼ最適なもののうち，全体の公平さ（egalitarian）が最小の安定マッチングを求める問題を考える．我々は，この問題が NP 困難であることを示し，この問題に対して近似度が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 preferable for men but unpreferable for women, (or, if we exchange the role of men and women, the resulting matching is woman-optimal). The sex-equal stable marriage problem, posed by Gusfield and Irving, asks to find a stable matching ``fair'' for both genders, namely it asks to find a stable matching with the property that the sum of the men's score 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 {\em a near optimal} solution in the sex-equal stable marriage problem. Furthermore, we consider the problem of optimizing 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 NP-hard, and give a polynomial time algorithm whose approximation ratio is less than two. |
|
| キーワード | （和） | 安定結婚問題 / 男女平等安定マッチング問題 / 近似アルゴリズム / / / / / |
| （英） | the stable marriage problem / the sex-equal stable marriage problem / approximation algorithms / / / / / | |
| 文献情報 | 信学技報, vol. 107, no. 537, COMP2007-55, pp. 1-8, 2008年3月. | |
| 資料番号 | COMP2007-55 | |
| 発行日 | 2008-03-03 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2007-55 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2008-03-10 - 2008-03-10 |
| 開催地（和） | 日本アイ・ビー・エム（株）大和事業所 |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2008-03-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 男女平等安定マッチング問題に対する近似アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Approximation Algorithms for the Sex-Equal Stable Marriage Problem |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 安定結婚問題 / the stable marriage problem |
| キーワード(2)（和/英） | 男女平等安定マッチング問題 / the sex-equal stable marriage problem |
| キーワード(3)（和/英） | 近似アルゴリズム / approximation algorithms |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 柳澤 弘揮 / Hiroki Yanagisawa / ヤナギサワ ヒロキ |
| 第1著者 所属（和/英） | 日本アイ・ビー・エム株式会社 (略称： 日本IBM) IBM (略称： IBM) |
| 第2著者 氏名（和/英/ヨミ） | 宮崎 修一 / Shuichi Miyazaki / ミヤザキ シュウイチ |
| 第2著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 岩間 一雄 / Kazuo Iwama / イワマ カズオ |
| 第3著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2008-03-10 09:30:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2007-55 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | no.537 |
| ページ範囲 | pp.1-8 |
| ページ数 | 8 |
| 発行日 | 2008-03-03 (COMP) |
[研究会発表申込システムのトップページに戻る]