Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting

Simple item page
dc.creatorStefankovic, Daniel
dc.creatorVempala, Santosh
dc.creatorVigoda, Eric
dc.date2006-12-10
dc.date.accessioned2026-07-07T07:31:52Z
dc.date.available2026-07-07T07:31:52Z
dc.descriptionWe present a near-optimal reduction from approximately counting the cardinality of a discrete set to approximately sampling elements of the set. An important application of our work is to approximating the partition function $Z$ of a discrete system, such as the Ising model, matchings or colorings of a graph. The typical approach to estimating the partition function $Z(β^*)$ at some desired inverse temperature $β^*$ is to define a sequence, which we call a {\em cooling schedule}, $β_0=0<β_1<...<β_\ell=β^*$ where Z(0) is trivial to compute and the ratios $Z(β_{i+1})/Z(β_i)$ are easy to estimate by sampling from the distribution corresponding to $Z(β_i)$. Previous approaches required a cooling schedule of length $O^*(\ln{A})$ where $A=Z(0)$, thereby ensuring that each ratio $Z(β_{i+1})/Z(β_i)$ is bounded. We present a cooling schedule of length $\ell=O^*(\sqrt{\ln{A}})$. For well-studied problems such as estimating the partition function of the Ising model, or approximating the number of colorings or matchings of a graph, our cooling schedule is of length $O^*(\sqrt{n})$, which implies an overall savings of $O^*(n)$ in the running time of the approximate counting algorithm (since roughly $\ell$ samples are needed to estimate each ratio).
dc.identifierhttps://arxiv.org/abs/cs/0612058
dc.identifierhttp://arxiv.org/abs/cs/0612058
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/118911
dc.subjectData Structures and Algorithms
dc.subjectDiscrete Mathematics
dc.subjectG.3
dc.titleAdaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting
dc.typetext

Files

Collections

arXiv