抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
古典的分散グラフ問題において,グラフ上の各インスタンスは,実行可能解の空間(例えば,すべての適切(Δ+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・京大機械翻訳】