Paper Info
Title
A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid
Abstract
We investigate the computational difficulty of approximating the partition function of the ferromagnetic Ising model on a regular matroid. Jerrum and Sinclair have shown that there is a fully polynomial randomised approximation scheme (FPRAS) for the class of graphic matroids. On the other hand, the authors have previously shown, subject to a complexity-theoretic assumption, that there is no FPRAS for the class of binary matroids, which is a proper superset of the class of graphic matroids. In order to map out the region where approximation is feasible, we focus on the class of regular matroids, an important class of matroids which properly includes the class of graphic matroids, and is properly included in the class of binary matroids. Using Seymour's decomposition theorem, we give an FPRAS for the class of regular matroids.
Year
DOI
Venue
2011
10.1007/978-3-642-22006-7_44
Clinical Orthopaedics and Related Research
Keywords
DocType
Volume
ferromagnetic ising model,binary matroids,graphic matroids,complexity-theoretic assumption,partition function,decomposition theorem,regular matroids,polynomial-time algorithm,important class,computational difficulty,regular matroid,polynomial randomised approximation scheme,ising model,tutte polynomial,approximation algorithms,matroids
Conference
abs/1010.6231
Issue
ISSN
Citations 
3
SICOMP 42(3) 1132-1157 (2013)
8
PageRank 
References 
Authors
0.62
11
2
Name
Order
Citations
PageRank
leslie ann goldberg11411125.20
mark jerrum22755564.62