Adaptive simulated annealing: A near-optimal connection between sampling and counting

DOI10.1145/1516512.1516520zbMath1325.68198OpenAlexW2088847343MaRDI QIDQ3452215

Eric Vigoda, Daniel Štefanković, Santosh Vempala

Publication date: 11 November 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.211.9581

zbMATH Keywords

Markov chain Monte Carlosimulated annealingcounting

Mathematics Subject Classification ID

Sampling theory, sample surveys (62D05) Learning and adaptive systems in artificial intelligence (68T05) Combinatorial probability (60C05)

Related Items

Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction, Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs, A practical volume algorithm, Efficient sampling and counting algorithms for the Potts model on ℤ^d at all temperatures, Fast algorithms at low temperatures via Markov chains†, Algorithms for hard-constraint point processes via discretization, Inapproximability of counting independent sets in linear hypergraphs, Unnamed Item, Unnamed Item, Improved mixing condition on the grid for counting and sampling independent sets, Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model, Likelihood-based inference for Matérn type-III repulsive point processes, Using TPA to count linear extensions, Random Construction of Interpolating Sets for High-Dimensional Integration, Counting subsets of contingency tables, Quantum Chebyshev's Inequality and Applications, Approximately counting bases of bicircular matroids, Randomly coloring constant degree graphs, Unnamed Item, Approximation algorithms for the normalizing constant of Gibbs distributions, Improved inapproximability results for counting independent sets in the hard-core model