PowerPoint プレゼンテーション

C09
ネットワーク問題のモデル化と
アルゴリズムの研究
伊藤大雄(京大)
岩間一雄(京大)
増澤利光(阪大)
宮崎修一(京大)
堀山貴史(埼玉大)
今回紹介する成果
•
•
•
•
•
P2P探索の効率化
安定結婚問題の近似アルゴリズム
競合比の自動証明
孤立クリーク・密部分グラフの列挙
組合せゲーム・パズルの成果
Peer to Peer (P2P) 探索の効率化
• P2Pファイル共有システム
– ピア（Peer）間の直接通信によるファイル交換
– 例：Napster, Gnutella, BitTorrent, Winny
• 探索問題
– 目的オブジェクト（ファイル等）を持つピアの探索
– 最適化
• 探索に要するメッセージ数の最小化
• 探索問題の難しさ
– 莫大な数のピア
– 動的ネットワーク環境（ノードの参加・離脱）
適応的な分散型解法が必要
ランダム探索モデル
B
A
A： Searcher
：Object
B： Owner
： Index
• ランダム探索 (Miura, Tagawa, Kakugawa, IEEE TPDS, 2006)
– ファイル所有者はインデックスをランダムに散布
– 探索者はランダムに探索クエリーを送付
インデックス数
少
多
インデッスク散布・更新コスト
小
大
探索コスト
大
小
散布・更新コストと
探索コストの
トレードオフ
研究成果（１）
• システム全体の総通信コストの最小化
– 総コスト：（インデックス散布・更新コスト）
＋（探索コスト）＊（探索頻度）
– オブジェクトの探索頻度に応じてインデックス数を最適化
通信コスト
8.E+06
6.E+06
提案手法
既存手法
α：Zipf 係数
4.E+06
2.E+06
0.E+00
α=0.6
α=0.8
α=1.0
α=1.2
研究成果（２）
• 自己適応型の探索アルゴリズム
ファイルの探索頻度（人気度）の変化
総コストの最適化（インデックス数の自己最適化）
1.E+05
理論最小値
1.E+05
提案手法
提案手法
通信コスト
8.E+04
通信コスト
理論最小値
1.E+05
6.E+04
4.E+04
8.E+04
6.E+04
4.E+04
2.E+04
2.E+04
0.E+00
0.E+00
T
2T
3T
4T
5T
6T
人気度が連続変化する場合
7T
2T
4T
6T
8T
10T
人気度が離散変化する場合
安定結婚問題
入力：男性 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
安定結婚問題の応用
病院－研修医
NRMP (National Resident Matching Program)
CaRMS (Canadian Resident Matching Service)
SPA (Scottish Pre-registration house officer Allocations)
JRMP (Japanese Resident Matching Program)
学校－生徒
Singapore [Teo, Sethuraman, Tan 1999]
本特定領域研究での成果
同順位と不完全リストを許す拡張に対して最大サイズの安定
マッチングを求めることはＮＰ困難であることが知られていた。こ
の問題に対して多項式時間近似アルゴリズムを与えた。
log N
N
1
・ 2-c
√N
・ 2-c
[Iwama, Miyazaki, Okamoto; SWAT 2004, IEICE Trans. 2006]
[Iwama, Miyazaki, Yamauchi; ISAAC 2005]
・ 1.875
[Iwama, Miyazaki, Yamauchi; SODA 2007]
・ 1.8
[現在]
男女にできるだけ平等な安定マッチングを求める問題はNP完全であること
が知られていた。この問題に対し近似アルゴリズムを与えた。[Iwama,
Miyazaki, Yanagisawa; WADS 2007]
オンライン・アルゴリズムの性能保証
• 競合比の解析
– 将来の情報なしに、いかにうまい行動をとるか
– 将来の情報をすべて知っている場合の最良の選択に
どれだけ迫れるか
競合比＝
オフラインの利得
の最悪値
オンラインアルゴリズムの利得
より良い競合比を示すには、詳細な場合分けに基づく
アルゴリズム設計と競合比解析が必要
オンライン・アルゴリズムの性能保証
• 競合比の解析
計算機の援用
競合比改善のアイデアはあっても、
– 将来の情報なしに、いかにうまい行動をとるか
による
場合分けが膨大となるため、
– 将来の情報をすべて知っている場合の最良の選択に
自動解析
証明が困難
どれだけ迫れるか
競合比＝
オフラインの利得
の最悪値
オンラインアルゴリズムの利得
より良い競合比を示すには、詳細な場合分けに基づく
アルゴリズム設計と競合比解析が必要
競合比の自動解析
•
２ビンのオンラインナップザック問題
–
–
•
競合比上界 1.334
下界 1.281
→ 1.301 （上下限一致）
（人手による解析）
アイデア（無限を有限におさえる）
–
アルゴリズムの状態の遷移を自動生成、
各状態で競合比解析
– アイテムを大きさをクラス分けして扱い、入力を網羅
– クラスに基づくと、ビンの状態は有限
– SS + LL ≦１ or ＞１等の場合分けを自動生成
状態遷移図
276状態
1. 状態遷移をすべて列挙
2. 各状態で競合比 ≦ 1.3334 を証明
孤立クリーク・密部分グラフの列挙
• クリーク列挙：ウェブ探索などで近年注目されている。
• しかしクリークの問題は難しい・・・
– 最大クリーク発見問題⇒近似比: Ω (n1-ε ) [Hastad 99]
– 極大クリーク列挙⇒指数(Θ(3n/3))個ありうる[Moon, et al. 65]
• そこで我々は・・・孤立クリークを導入
< ck 本の枝
k 節点
• 全c-孤立クリークをO(c422cm)時間で列挙！
• さらにc=O(1)⇔線形時間、c=O(logn)⇔多項式時間を証明。
孤立クリーク・密部分グラフの列挙
• 擬クリークPC(α,β): 誘導部分グラフの平均次数≧αかつ
最小次数≧β、を定義し、
1-孤立擬クリーク


k
1
k  (logk) ,
(ε>0)に対し、「ε=0 PC
⇔ 
多項式時間列挙可能」を証明。
1 
(logk) 

• 1-孤立２部クリークに対し、
– それが指数個存在し得ること
– 部の大きさの比が定数のときの多項式時間総列挙ア
ルゴリズム

を示した。
組合せゲーム・パズルの成果
• 半順序集合ゲーム（ニム、チョンプ等を含む古典的ゲー
ム）を拡張し重み付き半順序集合ゲームを提案。
– (0,1)重み：（重み無し）半順序ゲームに多項式時間帰着。
– 実数重み：半順序が全順序であるものに対する多項式時
間必勝手順。
• 一般化三並べ
– スネーキーの置き石１の必勝法
⇒スネーキーのハンディキャップ数は0か1。
今回紹介した成果
•
•
•
•
•
P2P探索の効率化
安定結婚問題の近似アルゴリズム
競合比の自動証明
孤立クリーク・密部分グラフの列挙
組合せゲーム・パズルの成果

Download Report