Approximate counting via random optimization
Alexander I. Barvinok · Random Structures and Algorithms · 1997
Let F F be a family of subsets of 1, . . ., n .We propose a simple randomized n algorithm to estimate the cardinality of F F from the maximum weight of a subset X g F F in n n Ä 4 a random weighting of 1, . . ., n .The examples include enumeration of perfect matchings in graphs, bases in matroids, and Hamiltonian cycles in graphs.