文献

J-GLOBAL ID：202002260730571681   整理番号：20A2461387

8バーテックス模型の近似可能性【JST・京大機械翻訳】

Approximability of the eight-vertex model

著者 (4件)： Cai Jin-Yi (University of Wisconsin-Madison) ,  Liu Tianyu (University of Wisconsin-Madison) ,  Lu Pinyan (Shanghai University of Finance and Economics, China) ,  Yu Jing (Georgia Institute of Technology)
資料名： ACM Proceedings  (ACM Proceedings)
号： CCC ’20  ページ： 1-18  発行年： 2020年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 4-正規グラフ上で定義された8頂点モデルの近似複雑度の分類の研究を開始した。8頂点モデルは,その特殊ケースと共に,6頂点モデルが,統計的物理学における最も広く研究されたモデルの1つであり,グラフ理論における加重方向を計数する問題として記述することができる。結果は,モデルのパラメータに従って分類されたすべての4つの正規グラフに関する分割関数の近似性に関するものである。著者らの複雑性結果は,物理からの相転移現象と一致した。8頂点モデルの量子分解を導入し,パラメータ空間のさまざまな領域における一連の閉鎖特性を証明した。さらに,4正規平面グラフに余分な閉鎖特性があることを示した。パラメータ空間のこれらの領域は相転移閾値と一致した。これらの閉鎖特性を用いて,Markov連鎖モンテカルロを介して多項式時間近似アルゴリズムを導いた。また,8頂点モデルが相転移閾値の他の側面に近似するNP困難であることを示した。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： モンテカルロ法 ,  相転移 ,  グラフ理論 ,  平面グラフ ,  Markov連鎖 ,  *近似法 ,  類似性 ,  *バーテックス模型 ,  NP困難
準シソーラス用語： パラメータ空間 ,  近似アルゴリズム ,  複雑性 ,  多項式時間 ,  複雑度 , 【Automatic Indexing@JST】

著者キーワード (3件)： 近似複雑性 ,  マルコフ連鎖モンテカルロ ,  8バーテックスモデル

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (3件)： バーテックス模型 ,  近似 ,  可能性