资源描述：
《《安定结婚问题対》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、安定結婚問題に対する1.875-近似アルゴリズム岩間一雄 宮崎修一 山内直哉（京都大学）科学研究費特定領域研究平成18年度第2回全体会議2006.11.18発表内容安定結婚問題に関する、ある最大化問題(MAXSMTI)→ＮＰ-hard、近似度の下限1.105unlessP=NP[Halldorssonet.al.2003]2-近似アルゴリズムは簡単↓↓↓-近似アルゴリズム(cは定数)[Iwama,et.al.2004](2-c)NlogN(2-c)N1√1.875-近似アルゴリズム[今日]-近似アルゴリズム(cは定数)[Iwama,et.al.2
2、005]入力：男性N人女性N人希望リスト安定結婚問題とはN=5の例1:acbdea:213452:caebdb:214533:baedcc:123544:cbdead:314255:cdbeae:43125男性の希望リスト 女性の希望リスト男性：1,2,3,4,5女性：a,b,c,d,e1a2b3c4d5e出力：男女間のマッチング1:acbdea:213452:caebdb:214533:baedcc:123544:cbdead:314255:cdbeae:43125これは解の条件を満たしていない。安定結婚問題: 与えられた入力から、安
3、定マッチングを見つける。男性1と女性cはブロッキングペアブロッキングペアの存在しないマッチング:安定マッチング安定結婚問題・最初の論文 →[Gale&Shapley1962]-アメリカの研修医配属問題がきっかけ。-どんな例題にも、必ず安定マッチングが存在する。-安定マッチングを多項式時間で見つけることができる。(Gale-Shapleyアルゴリズム)・様々な類似問題-安定ルームメイト問題-Residents/Hospitals問題・最近、様々な新種の問題・実世界での応用研修医配属NRMP(NationalResidentMatchingProgram
4、)CaRMS(CanadianResidentMatchingService)SPA(ScottishPre-registrationhouseofficerAllocations)JRMP(JapaneseResidentMatchingProgram)1:acbdea:213452:caebdb:214533:baedcc:123544:cbdead:314255:cdbeae:43125TheGale-ShapleyAlgorithm[Gale&Shapley1962](Men-propose）××××××××Theorem[Gale&Shap
5、ley1962,Gusfield&Irving1989]TheGale-Shapleyalgorithmfindsastablematching.証明Supposenotstable.Thereisablockingpair.2:・・・ e ・・・e:・・・ 2 ・・・Duringthealgorithmexecution,“2”madeaproposalto“e”,buthewasrejected.e:・・・ 2 ・・・×Atthismoment,“e”hadapartnerbetterthan“2”.Afterthat,shemaychangea
6、partner,butneverbecomesworse.acontradiction(Q.E.D.)×希望リストの制限2:caebd希望リストは全順序かつ完全。希望リストの制限緩和2:(ca)(eb)d2:cae(1)同順位リスト(2)不完全リストOriginalStableMarriageproblem(SM)StableMarriagewithTies(SMT)StableMarriagewithIncompletelists(SMI)安定結婚問題の例題の制限緩和（１） 同順位リスト (SMT)1:a(cbd)ea:213452:caebdb:
7、(21)4533:ba(ed)cc:123544:cbd(ea)d:(314)(25)5:c(db)eae:43125(5,c) はブロッキングペア。(1,c)はブロッキングペアではない。(3,d)はブロッキングペアではない。定理[Gusfield&Irving1989]任意のSMT例題は、少なくとも1つ安定マッチングを持つ。（証明）1:a(cbd)ea:213452:caebdb:(21)4533:ba(ed)cc:123544:cbd(ea)d:(314)(25)5:c(db)eae:43125SMT 例題同順位を適当にばらす1:abcdea:2
8、13452:caebdb:124533:baedcc:123544:cbdaed:314255:cdbeae
