2006/12/10 by Stefankovic, Daniel, Vempala, Santosh, Vigoda, Eric · 1 citation
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.3
paper · doi:10.48550/arxiv.cs/0612058
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(β^*) at some desired inverse temperature β^* is to define a sequence, which we call a \em cooling schedule, β0=0