Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
From MaRDI portal
Publication:5886117
DOI10.1017/S0963548321000080MaRDI 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
68Q25: Analysis of algorithms and problem complexity
60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
82B20: Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
68W20: Randomized algorithms
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
