2010/10/31 by Leslie Ann Goldberg, Mark Jerrum · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Approximation algorithm #Binary number #Class (philosophy) #Complexity and Algorithms in Graphs #Function (biology) #Ising model #Markov Chains and Monte Carlo Methods #Matroid #Partition (number theory) #Partition function (quantum field theory) #Time complexity #cs.CC #math.CO #msc:05B35 #msc:68W25 #msc:82B20
paper · pdf · doi:10.1137/110851213
published in SIAM Journal on Computing 42(3), 1132-1157 (Society for Industrial and Applied Mathematics) · New Lemma 4 provides a smoother derivation of the two lemmas now numbered 5 and 6. The old Lemma 2 is not now needed, and the appendix is shorter. Various clarifications have been made and typos corrected
openalex publication_date 2013/01/01 · arxiv created 2013/04/22 · arxiv updated 2013/08/01 · openalex created_date 2017/10/20 · openalex updated_date 2026/08/05
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 randomized 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.