Computer Science – Computational Complexity
Scientific paper
2010-10-29
Computer Science
Computational Complexity
Scientific paper
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.
Goldberg Leslie Ann
Jerrum Mark
No associations
LandOfFree
A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-615988