Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
From MaRDI portal
Publication:5886117
DOI10.1017/S0963548321000080OpenAlexW3155378399MaRDI QIDQ5886117
Martin Dyer, Haiko Müller, Marc Heinrich, Mark R. Jerrum
Publication date: 30 March 2023
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2005.07944
Analysis of algorithms and problem complexity (68Q25) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Holant problems for 3-regular graphs with complex edge functions
- A polynomial characterization of some graph partitioning problems
- Some simplified NP-complete graph problems
- Maximum cut on line and total graphs
- From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
- Ground states, residual entropies, and specific heat capacity properties of frustrated Ising system on pyrochlore lattice in effective field theory cluster approximations
- Some applications of Wagner's weighted subgraph counting polynomial
- Polynomial-Time Approximation Algorithms for the Ising Model
- Adaptive simulated annealing: A near-optimal connection between sampling and counting
- Graphical Models, Exponential Families, and Variational Inference
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- Canonical Paths for MCMC: from Art to Science
- Complexity Dichotomies for Counting Problems
- Fast convergence of the Glauber dynamics for sampling independent sets
- Random sampling of 3‐colorings in ℤ2
- Statistical Mechanics of Lattice Systems
- Statistics of Kagomé Lattice
