C09 ネットワーク問題のモデル化と アルゴリズムの研究

Slides:



Advertisements
Similar presentations
組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
Advertisements

©2008 Ikuo Tahara探索 状態空間と探索木 基本的な探索アルゴリズム 横形探索と縦形探索 評価関数を利用した探索アルゴリズム 分岐限定法 山登り法 最良優先探索 A ( A* )アルゴリズム.
効率的に計算可能な 加法的誤りの訂正可能性 安永 憲司 九州先端科学技術研究所 SITA 2012 @ 別府湾ロイヤルホテル
Lecture02-Binary Search Trees 通信情報システム専攻 岩間伊藤研究室 M1 前田圭介.
ハノイグラフの生成と最短経路の導出 東京電機大学 理工学部 村田和也 松浦昭洋
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
2行+αチョンプに関する考察 京都大学 ○後藤順一 伊藤大雄.
セキュアネットワーク符号化構成法に関する研究
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
ラベル付き区間グラフを列挙するBDDとその応用
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
秘密のリンク構造を持つグラフのリンク解析
半順序集合ゲーム周期性定理の拡張 京都大学情報学研究科 ○後藤順一 伊藤大雄.
先端論文紹介ゼミ Tracking control for nonholonomic mobile robots: Integrating the analog neural network into the backstepping technique 非ホロノミック移動ロボットのための追従制御:
5.チューリングマシンと計算.
5.チューリングマシンと計算.
An Algorithm for Enumerating Maximal Matchings of a Graph
分子生物情報学 動的計画法に基づく配列比較法 (ペアワイズアライメント法)
Approximation of k-Set Cover by Semi-Local Optimization
Reed-Solomon 符号と擬似ランダム性
上坂吉則 尾関和彦 文一総合出版 宮崎大輔2003年6月28日(土)
リンク構造を考慮したベクトル空間法によるWebグラフ分割手法に関する研究
先端論文紹介ゼミ Role-based Context-specific Multiagent Q-learning
データ構造と アルゴリズム 第二回 知能情報学部 新田直也.
9.NP完全問題とNP困難問題.
岩井 儀雄 コンピュータ基礎演習  ー探索、整列ー 岩井 儀雄
高山建志 五十嵐健夫 テクスチャ合成の新たな応用と展開 k 情報処理 vol.53 No.6 June 2012 pp
計算量理論輪講 岩間研究室 照山順一.
情報工学総合演習 D-I 近似アルゴリズム 埼玉大学 理工学研究科 山田 敏規、 橋口 博樹、 堀山 貴史
k 個のミスマッチを許した点集合マッチング・アルゴリズム
ネットワーク上での社会的効用と個人的効用の対立問題に対するアルゴリズム的研究
奈良女子大集中講義 バイオインフォマティクス (9) 相互作用推定
定兼邦彦 今井浩 東京大学理学系研究科 情報科学専攻
7.4 Two General Settings D3 杉原堅也.
実行時情報に基づく OSカーネルのコンフィグ最小化
第14章 モデルの結合 修士2年 山川佳洋.
第3回 アルゴリズムと計算量 2019/2/24.
Internet広域分散協調サーチロボット の研究開発
安定結婚問題に対する 近似アルゴリズム 岩間一雄 宮崎修一 山内直哉 (京都大学) 科学研究費特定領域研究
計算量理論輪講 chap5-3 M1 高井唯史.
2009年12月4日 ○ 前田康成(北見工業大学) 吉田秀樹(北見工業大学) 鈴木正清(北見工業大学) 松嶋敏泰(早稲田大学)
Data Clustering: A Review
連続領域におけるファジィ制約充足問題の 反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学.
Webコミュニティ概念を用いた Webマイニングについての研究 A study on Web Mining Based on Web Communities 清水 洋志.
バイトコードを単位とするJavaスライスシステムの試作
Number of random matrices
ベイジアンネットワーク概説 Loopy Belief Propagation 茨城大学工学部 佐々木稔
P2P ネットワーク上で 実時間ストリーミングを実現するための 分散制御プロトコルの提案
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
Peer-to-Peerシステムにおける動的な木構造の生成による検索の高速化
モデル検査(5) CTLモデル検査アルゴリズム
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
B03 量子論理回路の 最適化に関する研究 西野哲朗,垂井淳,太田和夫,國廣昇 電気通信大学 情報通信工学科.
Lecture 8 Applications: Direct Product Theorems
第9回 優先度つき待ち行列,ヒープ,二分探索木
直並列グラフの連続多重彩色 西関研究室 吉田進太郎.
大規模ネットワークに対する 実用的クラスタ発見アルゴリズムの開発
5.チューリングマシンと計算.
Max Cut and the Smallest Eigenvalue 論文紹介
保守請負時を対象とした 労力見積のためのメトリクスの提案
A02 計算理論的設計による知識抽出モデルに関する研究
GbEにおける TCP/IP の研究について
擬似クリークを列挙する 多項式時間遅延アルゴリズム
参考:大きい要素の処理.
Speaker: Kazuhiro Inaba Paper Introduction from WSDM 2015
13.近似アルゴリズム.
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
インセンティブにより自律ユーザに 高品質なオーバーレイマルチキャスト木を 構築させるプロトコルの提案
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
京都大学 情報学研究科 通信情報システム専攻 高田智史 joint work with 伊藤大雄 中村義作
Presentation transcript:

C09 ネットワーク問題のモデル化と アルゴリズムの研究 伊藤大雄(京大)  岩間一雄(京大)  増澤利光(阪大)  宮崎修一(京大)  堀山貴史(埼玉大)

今回紹介する成果 P2P探索の効率化 安定結婚問題の近似アルゴリズム 競合比の自動証明 孤立クリーク・密部分グラフの列挙 組合せゲーム・パズルの成果

Peer to Peer (P2P) 探索の効率化 例:Napster, Gnutella, BitTorrent, Winny 探索問題 目的オブジェクト(ファイル等)を持つピアの探索 最適化 探索に要するメッセージ数の最小化 探索問題の難しさ 莫大な数のピア 動的ネットワーク環境(ノードの参加・離脱) 超大規模Peer-to-Peerネットワークにおけるオブジェクト検索(情報検索) 適応的な分散型解法が必要 3

散布・更新コストと 探索コストの トレードオフ ランダム探索モデル A B B: Owner : Index :Object A: Searcher ランダム探索 (Miura, Tagawa, Kakugawa, IEEE TPDS, 2006) ファイル所有者はインデックスをランダムに散布 探索者はランダムに探索クエリーを送付 超大規模Peer-to-Peerネットワークにおけるオブジェクト検索(情報検索)のためのインデックス情報(情報の所在場所を表すデータ)散布方式 インデックス情報をランダムに散布する手法:通信コストをかけてインデックス情報を多く配布すれば検索時には低コストでインデックス情報を発見でき,逆にインデックス情報の配布を少なくすれば検索時にはインデックス情報の発見に通信コストがかかるという,トレードオフの関係がある. 散布・更新コストと 探索コストの トレードオフ インデックス数 少 多 インデッスク散布・更新コスト 小 大 探索コスト 4

研究成果(1) システム全体の総通信コストの最小化 総コスト:(インデックス散布・更新コスト) +(探索コスト)*(探索頻度) 総コスト:(インデックス散布・更新コスト)            +(探索コスト)*(探索頻度) オブジェクトの探索頻度に応じてインデックス数を最適化 システム全体の総通信コストの最小化:オブジェクトの探索頻度(人気度)に応じて、散布インデックス数と散布タイミングを最適化することにより達成 5

研究成果(2) 自己適応型の探索アルゴリズム ファイルの探索頻度(人気度)の変化 総コストの最適化(インデックス数の自己最適化)      ファイルの探索頻度(人気度)の変化     総コストの最適化(インデックス数の自己最適化) 最適化法は各ノードの局所的な情報(受け取った検索要求頻度など)のみに基づいて最適化を行う点が特徴 つぎに提案手法の有効性を確認するために,計算機によるシミュレーション実験を行った.ノード数を20000とし,オブジェクトのアクセス頻度を変化させたときのシステム全体の通信コストに関して,提案手法と理論的最適値を比較したものがこの図である. 人気度が連続変化する場合 人気度が離散変化する場合 6

安定結婚問題 入力 :男性 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) 病院 - 研修医 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]

本特定領域研究での成果 同順位と不完全リストを許す拡張に対して最大サイズの安定マッチングを求めることはNP困難であることが知られていた。この問題に対して多項式時間近似アルゴリズムを与えた。 log N ・           [Iwama, Miyazaki, Okamoto; SWAT 2004, IEICE Trans. 2006] 2 - c N 1 ・         [Iwama, Miyazaki, Yamauchi; ISAAC 2005] 2 - c √ N ・ 1.875     [Iwama, Miyazaki, Yamauchi; SODA 2007]  ・ 1.8      [現在] 男女にできるだけ平等な安定マッチングを求める問題はNP完全であることが知られていた。この問題に対し近似アルゴリズムを与えた。[Iwama, Miyazaki, Yanagisawa; WADS 2007]

オンライン・アルゴリズムの性能保証 競合比の解析 競合比= オフラインの利得 オンラインアルゴリズムの利得 の最悪値 将来の情報なしに、いかにうまい行動をとるか 将来の情報をすべて知っている場合の最良の選択に   どれだけ迫れるか 競合比= オフラインの利得 オンラインアルゴリズムの利得 の最悪値 より良い競合比を示すには、詳細な場合分けに基づく アルゴリズム設計と競合比解析が必要

競合比改善のアイデアはあっても、場合分けが膨大となるため、 オンライン・アルゴリズムの性能保証 競合比改善のアイデアはあっても、場合分けが膨大となるため、 証明が困難 競合比の解析 将来の情報なしに、いかにうまい行動をとるか 将来の情報をすべて知っている場合の最良の選択に   どれだけ迫れるか 計算機の援用による 自動解析 競合比= オフラインの利得 オンラインアルゴリズムの利得 の最悪値 より良い競合比を示すには、詳細な場合分けに基づく アルゴリズム設計と競合比解析が必要

競合比の自動解析 2ビンの オンライン ナップザック 問題 → 1.301 (上下限 一致) アイデア (無限を有限におさえる) 競合比 上界 1.334 下界 1.281 アイデア (無限を有限におさえる) アルゴリズムの状態の遷移を自動生成、 各状態で競合比解析 アイテムを大きさをクラス分けして扱い、入力を網羅 クラスに基づくと、ビンの状態は有限 SS + LL ≦1 or >1 等の場合分けを自動生成 → 1.301 (上下限 一致) (人手による解析)

状態遷移図 276状態 状態遷移をすべて列挙 2. 各状態で 競合比 ≦ 1.3334 を証明

孤立クリーク・密部分グラフの列挙 < ck 本の枝 クリーク列挙:ウェブ探索などで近年注目されている。 しかしクリークの問題は難しい・・・ 最大クリーク発見問題⇒近似比: Ω (n1-ε ) [Hastad 99] 極大クリーク列挙⇒指数(Θ(3n/3))個ありうる[Moon, et al. 65] そこで我々は・・・孤立クリークを導入 全c-孤立クリークをO(c422cm)時間で列挙! さらにc=O(1)⇔線形時間、c=O(logn)⇔多項式時間を証明。 k 節点 < ck 本の枝

孤立クリーク・密部分グラフの列挙 擬クリークPC(α,β): 誘導部分グラフの平均次数≧αかつ最小次数≧β、を定義し、                                                      1-孤立擬クリーク                                                          (ε>0)に対し、「ε=0 ⇔ 多項式時間列挙可能」を証明。 1-孤立2部クリークに対し、 それが指数個存在し得ること 部の大きさの比が定数のときの多項式時間総列挙アルゴリズム   を示した。

組合せゲーム・パズルの成果 半順序集合ゲーム(ニム、チョンプ等を含む古典的ゲーム)を拡張し重み付き半順序集合ゲームを提案。 一般化三並べ (0,1)重み:(重み無し)半順序ゲームに多項式時間帰着。 実数重み:半順序が全順序であるものに対する多項式時間必勝手順。 一般化三並べ スネーキーの置き石1の必勝法          ⇒スネーキーのハンディキャップ数は0か1。

今回紹介した成果 P2P探索の効率化 安定結婚問題の近似アルゴリズム 競合比の自動証明 孤立クリーク・密部分グラフの列挙 組合せゲーム・パズルの成果