Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs

Martin Dyer, Marc Heinrich, Mark Jerrum +1

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 al…