《安定结婚问题対》PPT课件.ppt

安定結婚問題対 1.875-近似 岩間一雄 宮崎修一 山内直哉 （京都大学） 科学研究費特定領域研究 平成18年度第2回全体会議 2006.11.18 発表内容 安定結婚問題関、最大化問題 (MAX SMTI) -hard、近似度下限 1.105 unless P=NP Halldorsson et.al. 2003 2-近似簡単 - 近似 (c定数) Iwama, et. al. 2004 (2 - c ) N log N (2 - c ) N 1 1.875-近似 今日 - 近似 (c定数) Iwama, et. al. 2005 入力：男性N人 女性N人 希望 安定結婚問題安定結婚問題 N=5例 1: a c b d e a: 2 1 3 4 5 2: c a e b d b: 2 1 4 5 3 3: b a e d c c: 1 2 3 5 4 4: c b d e a d: 3 1 4 2 5 5: c d b e a e: 4 3 1 2 5 男性希望 女性希望男性希望 女性希望 男性：男性： 1,2,3,4,5 1,2,3,4,5 女性：女性： a, a,b b, ,c c, ,d d,e ,e 1 a 2 b 3 c 4 d 5 e 出力 ：男女間 1: a c b d e a: 2 1 3 4 5 2: c a e b d b: 2 1 4 5 3 3: b a e d c c: 1 2 3 5 4 4: c b d e a d: 3 1 4 2 5 5: c d b e a e: 4 3 1 2 5 解条件満。解条件満。 安定結婚問題安定結婚問題: : 与入力、安定見。 与入力、安定見。 男性男性 1 1 女性女性 c c 存在存在: : 安定安定 安定結婚問題 最初論文 Gale & Shapley 1962 - 研修医配属問題。 - 例題、必安定存在。 - 安定多項式時間見。 (Gale-Shapley ) 様類似問題 - 安定問題 - Residents/Hospitals 問題 最近、様新種問題 実世界応用 研修医配属 NRMP (National Resident Matching Program) CaRMS (Canadian Resident Matching Service) SPA (Scottish Pre-registration house officer Allocations) JRMP (Japanese Resident Matching Program) 1: a c b d e a: 2 1 3 4 5 2: c a e b d b: 2 1 4 5 3 3: b a e d c c: 1 2 3 5 4 4: c b d e a d: 3 1 4 2 5 5: c d b e a e: 4 3 1 2 5 The Gale-The Gale-ShapleyShapley Algorithm Algorithm Gale & Gale & ShapleyShapley 1962 1962 (Men-propose(Men-propose） Theorem Gale & Theorem Gale & ShapleyShapley 1962, 1962, GusfieldGusfield & Irving 1989 & Irving 1989 The Gale-The Gale-ShapleyShapley algorithm finds a stable matching. algorithm finds a stable matching. 証明 Suppose not stable.There is a blocking pair. 2: e e: 2 During the algorithm execution, “2” made a proposal to “e”, but he was rejected. e: 2 At this moment, “e” had a partner better than “2”. After that, she may change a partner, but never becomes worse. a contradiction (Q.E.D.) 希望制限 2: c a e b d 希望全順序完全。 希望制限緩和 2: (c a) (e b) d 2: c a e (1) 同順位 (2) 不完全 Original Stable Marriage problem (SM) Stable Marriage with Ties (SMT) Stable Marriage with Incomplete lists (SMI) 安定結婚問題例題制限緩和 （） 同順位 (SMT) 1: a ( c b d ) e a: 2 1 3 4 5 2: c a e b d b: ( 2 1 ) 4 5 3 3: b a ( e d ) c c: 1 2 3 5 4 4: c b d ( e a ) d: ( 3 1 4 ) ( 2 5 ) 5: c ( d b ) e a e: 4 3 1 2 5 (5,c) 。 (1,c) 。 (3,d) 。 定理 Gusfield & Irving 1989 任意SMT例題、少1安定持。 （証明） 1: a ( c b d ) e a: 2 1 3 4 5 2: c a e b d b: ( 2 1 ) 4 5 3 3: b a ( e d ) c c: 1 2 3 5 4 4: c b d ( e a ) d: ( 3 1 4 ) ( 2 5 ) 5: c ( d b ) e a e: 4 3 1 2 5 SMT 例題 同順位適当 1: a b c d e a: 2 1 3 4 5 2: c a e b d b: 1 2 4 5 3 3: b a e d c c: 1 2 3 5 4 4: c b d a e d: 3 1 4 2 5 5: c d b e a e: 4 3 1 2 5 SM 例題 （） 不完全 (SMI) 1: a c b a: 2 1 3 4 5 2: c a b: 2 1 3: b a c: 1 2 4: c b d e d: 3 1 4 5: c d b e: 4 3 書人。 完全考慮必要。 (1,c) (4,d) (3,a) 定理 Gale & Sotomayor 1985 I : SMI 例題 M : I男性集合 W : I女性集合 M W以下分割。 M = M U M W = W U W s.t. I任意安定, M W 人相手。 M W 人独身。 2112 11 22 1 a 2 b 3 c 4 d 5 e 1 a 2 b 3 c 4 d 5 e 1 a 2 b 3 c 4 d 5 e SMI例題全安定同。 系 Gale-Shapley 使、多項式時間求 。 Stable Marriage (SM) Stable Marriage with Ties (SMT) Stable Marriage with Incomplete lists (SMI) 例題対安定同。 安定見簡単。 Stable Marriage with Ties and Incomplete lists (SMTI) 最大安定見簡単。 1: a a: ( 1 2 ) 2: a b b: 2 1 2 a b 1 2 a b 例題異安定持。 最大安定見問題非自明。 MAX SMTI 対近似可能性 近似困難性 近似可能性 NP-hard, 近似度下限 21/19 (1.105) unless P=NP Halldorsson, et. al. 2003 - 近似 (c定数) Iwama, et. al. 2004 (2 - c ) N log N (2 - c ) N 1 - 近似 (c定数) Iwama, et. al. 2005 2 - 近似簡単 1.875 - 近似 今回 c N log N c N N c N N MM ii M i+1 Procedure Increase Procedure Stabilize blocking pair (m, w) mw m is single or w is single m w mw m w |M | |M | There is no prohibited blocking pair (m,w) i i ii mw Increase 説明 Stabilize 説明（前一緒） M i Current matching Goal Increase the matching size. Prohibited blocking pairs may not arise. Remove edges and add 2 edges Increase the size by t Remove prohibited blocking pairs, by removing edges. If #