Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems

DOI10.1137/050644033zbMath1225.68270OpenAlexW2060222605WikidataQ56341081 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 Carlosimulated annealingcooling scheduleMarkov chainapproximate counting problems

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Exact enumeration problems, generating functions (05A15) Approximation methods and heuristics in mathematical programming (90C59) 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) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (17)

Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs ⋮ Sampling errors in nested sampling parameter estimation ⋮ Monte Carlo algorithms for computing \(\alpha \)-permanents ⋮ Employing the MCMC technique to compute the projection depth in high dimensions ⋮ Singular values of Gaussian matrices and permanent estimators ⋮ Fast algorithms at low temperatures via Markov chains† ⋮ Hitting time of quantum walks with perturbation ⋮ Unnamed Item ⋮ Characterizing optimal sampling of binary contingency tables via the configuration model ⋮ Counting proper colourings in 4-regular graphs via the Potts model ⋮ Rare event simulation and splitting for discontinuous random variables ⋮ Graph classes and the switch Markov chain for matchings ⋮ Sampling and Counting 3-Orientations of Planar Triangulations ⋮ Sampling Eulerian orientations of triangular lattice graphs ⋮ Counting Weighted Independent Sets beyond the Permanent ⋮ A reverse Sidorenko inequality ⋮ Approximation algorithms for the normalizing constant of Gibbs distributions

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