文献

J-GLOBAL ID：202002227157791431   整理番号：20A1865912

局所分散サンプリングと計数について【JST・京大機械翻訳】

On Local Distributed Sampling and Counting

著者 (2件)： Feng Weiming (Nanjing University, Nanjing, China) ,  Yin Yitong (Nanjing University, Nanjing, China)
資料名： ACM Proceedings  (ACM Proceedings)
号： PODC ’18  ページ： 189-198  発行年： 2018年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 古典的分散グラフ問題において,グラフ上の各インスタンスは,実行可能解の空間(例えば,すべての適切(Δ+1)-リストカラー)をグラフに指定し,分散アルゴリズムのタスクは,局所情報を用いて実行可能な解を構築することである。分散サンプリングと計数問題を研究し,その中で,各インスタンスが実行可能な解の結合分布を指定する。分散アルゴリズムのタスクは,この結合分布からサンプリングするか,あるいは限界確率を介して確率空間の体積を局所的に測定することである。後者のタスクは,計数の局所的対応物である推論としても知られている。インスタンスの自己還元性クラスのために,以下の等価性は,ポリ対数因子までのLOCALモデルで確立される:すべての関節分布,近似推論,および近似サンプリングは計算上等価である。局所制約によって定義されたすべての関節分布に対して,正確なサンプリングは上記のタスクの1つのいずれかに縮小できる。さらに,実行可能解を逐次的に構築することは,局所的に自明であり,次に,結合分布が強い空間混合を示すならば,上記のすべてのタスクは容易である。強い空間混合の最先端技術と結合して,著者らは,種々の重要なサンプリング問題のためのLOCALモデルにおける効率的サンプリングアルゴリズムを得る。非一意性領域におけるハードコアモデルに従ってサンプリングのための[3]において,[3]の下限をサンプリングするために,最大次数Δ,およびaO(log3n)-ラウンドアルゴリズムを有するグラフにおける正確なサンプリングマッチングのためのO(√Δlog3n)-ラウンドアルゴリズムを,分散サンプリングのための最初の計算相転移を与えた。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  相転移 ,  近似法 ,  還元性 ,  対数 ,  等価性 ,  非一意性 ,  分散アルゴリズム
準シソーラス用語： 近似推論 ,  グラフアルゴリズム , 【Automatic Indexing@JST】

著者キーワード (5件)： 分散グラフアルゴリズム ,  ギブス分布 ,  局所計算 ,  サンプリングアルゴリズム ,  強い空間混合

分類 (2件)： 図形・画像処理一般  (JE04010I) ,  人工知能  (JE08000Z)

タイトルに関連する用語 (2件)： サンプリング ,  計数