๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Approximate counting via random optimization

โœ Scribed by Alexander Barvinok


Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
177 KB
Volume
11
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

โœฆ Synopsis


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.


๐Ÿ“œ SIMILAR VOLUMES