Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems

DOI10.1137/050644033MaRDI QIDQ3532571zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ivona Bezáková, D. Štefankovič, Vijay V. Vazirani, Eric Vigoda

Publication date 28 October 2008

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/050644033

zbMATH Keywords

approximate counting problemscooling scheduleMarkov chainMonte Carlosimulated annealing

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Randomized algorithms (68W20) Approximation algorithms (68W25) Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Exploration of NP-hard enumeration problems by simulated annealing -- the spectrum values of permanents
• Adaptive simulated annealing: A near-optimal connection between sampling and counting
• Approximating the Permanent
• scientific article; zbMATH DE number 4131659
• Faster Simulated Annealing

Cited in

(22)

• Sampling Eulerian orientations of triangular lattice graphs
• Exploration of NP-hard enumeration problems by simulated annealing -- the spectrum values of permanents
• Sampling errors in nested sampling parameter estimation
• Hitting time of quantum walks with perturbation
• Counting proper colourings in 4-regular graphs via the Potts model
• Employing the MCMC technique to compute the projection depth in high dimensions
• Approximation algorithms for the normalizing constant of Gibbs distributions
• Monte Carlo algorithms for computing \(\alpha \)-permanents
• Rare event simulation and splitting for discontinuous random variables
• Sampling and counting 3-orientations of planar triangulations
• Adaptive simulated annealing: A near-optimal connection between sampling and counting
• Singular values of Gaussian matrices and permanent estimators
• scientific article; zbMATH DE number 828008 (Why is no real title available?)
• Characterizing optimal sampling of binary contingency tables via the configuration model
• Counting weighted independent sets beyond the permanent
• scientific article; zbMATH DE number 7650108 (Why is no real title available?)
• Graph classes and the switch Markov chain for matchings
• Fast algorithms at low temperatures via Markov chains†
• Parameter estimation for Gibbs distributions
• Counterexamples to conjectures on the occupancy fraction of graphs
• A reverse Sidorenko inequality
• Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs

This page was built for publication: Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3532571)