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

Markov chainsimulated annealingMonte Carlocooling scheduleapproximate counting problems

Mathematics Subject Classification ID

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

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

(21)

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

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)