Downloads: 151

Files in This Item:
File Description SizeFormat 
IEICE_tec.rep_COMP2007-55.pdf2.83 MBAdobe PDFView/Open
Title: 男女平等安定マッチング問題に対する近似アルゴリズム
Other Titles: Approximation Algorithms for the Sex-Equal Stable Marriage Problem
Authors: 柳澤, 弘揮  KAKEN_name
宮崎, 修一  KAKEN_id  orcid (unconfirmed)
岩間, 一雄  KAKEN_name
Author's alias: Yanagisawa, Hiroki
Miyazaki, Shuichi
Iwama, Kazuo
Keywords: 安定結婚問題
the stable marriage problem
the sex-equal stable marriage problem
approximation algorithms
Issue Date: 3-Mar-2008
Publisher: 電子情報通信学会
Journal title: 電子情報通信学会技術研究報告
Volume: 107
Issue: 537
Start page: 1
End page: 8
Thesis number: COMP2007-55
Abstract: 安定結婚問題は, 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 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.
Description: <コンピュテーション研究会(COMP)> 2008年 3月10日(月) 09:30 - 17:35, 日本アイ・ビー・エム(株)大和事業所 A館1階大教室
Rights: © 電子情報通信学会(IEICE)
Related Link:
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.