文献

J-GLOBAL ID：201702245376024654   整理番号：17A1637238

複雑性と最適性:不確実なグラフにおける出所目的地関係を解明する【Powered by NICT】

Complexity vs. optimality: Unraveling source-destination connection in uncertain graphs

著者 (5件)： Fu Xinzhe (Dept. of {Computer Science, Electronic Engineering}, Shanghai Jiao Tong University, China) ,  Xu Zhiying (Dept. of {Computer Science, Electronic Engineering}, Shanghai Jiao Tong University, China) ,  Peng Qianyang (Dept. of {Computer Science, Electronic Engineering}, Shanghai Jiao Tong University, China) ,  Fu Luoyi (Dept. of {Computer Science, Electronic Engineering}, Shanghai Jiao Tong University, China) ,  Wang Xinbing (Dept. of {Computer Science, Electronic Engineering}, Shanghai Jiao Tong University, China)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： INFOCOM  ページ： 1-9  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： ネットワークにおける宛先連結性の決定は基本的な問題となっている,既存の研究の多くは,ネットワークリンクにおける固有の不確実性を見落とすことを決定論的グラフに基づいている。このような限界を克服するために,本論文では,各辺eはいくつかの確率p(e)に独立して存在する不確実なグラフとしてネットワークをモデル化した。調べた問題は,源と宛先t,特定のノード対は道によって連結またはカットによって分離されているかどうかを決定することである。各決定過程は基本的なグラフと関連していると仮定して,各エッジの存在はc(e)のコストでエッジ試験により明らかにすることができた。著者らの目標は,生成物分布を形成する全ての可能な基礎となるグラフに渡って得られた予想と最小期待試験コストを最適戦略を見つけることである。組合せ最適化問題に定式化して,最初の不確実なグラフにおける宛先連結性を決定する最適の計算の複雑さを特性化した。具体的には,二つの密接に関連した問題のNP困難性を証明を通して,著者らは,決定論的グラフにおけるその対応物とは対照的に,この問題は,P=NPでなければ多項式時間で解くことができないことを示した。厳密なアルゴリズムを設計する必要性により,著者らは,最適戦略を導く動的計画法アルゴリズムをマルコフ決定過程フレームワークを適用した。厳密なアルゴリズムは,実際的な状況における禁止時間計算量を持つ可能性があるので,著者らはさらに最適性を二種類のさらに効果的な近似方式を提案した。1つ目は線形近似比率を持つ単純な欲張りアプローチである。興味深いことに,著者らは,ナイーブ,いくつかの他の一見より洗練されたアルゴリズムよりも匹敵する性能を持つことを示した。第二に,問題のサブモジュール性を発揮するためには,さらにより良い近似比を持つより複雑なアルゴリズムを設計した。提案したアルゴリズムの有効性を,三つの実際のネットワークデータセット上での包括的シミュレーション,そこからは,提案したアルゴリズムが従来の発見的方法よりも小さい期待費用と戦略をもたらすことを実証したを通して証明した。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： *グラフ ,  モデリング ,  アルゴリズム ,  発見的方法 ,  動的計画法 ,  計算量 ,  近似法 ,  NP困難 ,  *不確実性 ,  連結性 ,  ネットワーク ,  組合せ最適化問題
準シソーラス用語： 最適戦略 ,  決定論 ,  *最適性 , 【Automatic Indexing@JST】

分類 (1件)： 信頼性  (KB04040H)

タイトルに関連する用語 (3件)： 複雑性 ,  最適性 ,  グラフ