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
• DOI: 10.1002/(sici)1098-2418(199709)11:2<187::aid-rsa6>3.0.co;2-o

✦ 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.