Computer Science – Data Structures and Algorithms
Scientific paper
2006-12-10
Computer Science
Data Structures and Algorithms
Scientific paper
We 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(\beta^*)$ at some desired inverse temperature $\beta^*$ is to define a sequence, which we call a {\em cooling schedule}, $\beta_0=0<\beta_1<...<\beta_\ell=\beta^*$ where Z(0) is trivial to compute and the ratios $Z(\beta_{i+1})/Z(\beta_i)$ are easy to estimate by sampling from the distribution corresponding to $Z(\beta_i)$. Previous approaches required a cooling schedule of length $O^*(\ln{A})$ where $A=Z(0)$, thereby ensuring that each ratio $Z(\beta_{i+1})/Z(\beta_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).
Stefankovic Daniel
Vempala Santosh
Vigoda Eric
No associations
LandOfFree
Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-182922