Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems

DOI10.1137/050644033zbMath1225.68270WikidataQ56341081 ScholiaQ56341081MaRDI QIDQ3532571

Vijay V. Vazirani, Eric Vigoda, Ivona Bezáková, Daniel Štefanković

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

Monte Carlo; simulated annealing; cooling schedule; Markov chain; approximate counting problems

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05A15: Exact enumeration problems, generating functions

90C59: Approximation methods and heuristics in mathematical programming

60J10: Markov chains (discrete-time Markov processes on discrete state spaces)

60J20: Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)

68W25: Approximation algorithms

68W20: Randomized algorithms

Related Items

Characterizing optimal sampling of binary contingency tables via the configuration model, Counting Weighted Independent Sets beyond the Permanent, Unnamed Item, Graph classes and the switch Markov chain for matchings, Fast algorithms at low temperatures via Markov chains†, A reverse Sidorenko inequality, Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs, Sampling Eulerian orientations of triangular lattice graphs, 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, Singular values of Gaussian matrices and permanent estimators