论文标题
在线图上的抗铁磁ising模型的多项式时间近似算法
Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
论文作者
论文摘要
我们提出了多项式马尔可夫链蒙特卡洛算法，用于估计任何线图上的抗铁磁ising模型的分区功能。对算法的分析利用了McQuillan [Corr ABS/1301.2880（2013）]设计的“绕组”技术，并由Huang，Lu和Zhang [Proc。 27th Symp。在光盘上。算法（SODA16），514-527]。我们表明，即使对于线图，分区函数的精确计算也是＃p-hard，这表明近似算法是可以预期的最好的。我们还表明，ISING模型的Glauber动力学正在迅速在线图上混合，一个示例是Kagome晶格。
We present a polynomial-time Markov chain Monte Carlo algorithm for estimating the partition function of the antiferromagnetic Ising model on any line graph. The analysis of the algorithm exploits the "winding" technology devised by McQuillan [CoRR abs/1301.2880 (2013)] and developed by Huang, Lu and Zhang [Proc. 27th Symp. on Disc. Algorithms (SODA16), 514-527]. We show that exact computation of the partition function is #P-hard, even for line graphs, indicating that an approximation algorithm is the best that can be expected. We also show that Glauber dynamics for the Ising model is rapidly mixing on line graphs, an example being the kagome lattice.
