Premium
Approximate counting via random optimization
Author(s) -
Barvinok Alexander
Publication year - 1997
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199709)11:2<187::aid-rsa6>3.0.co;2-o
Subject(s) - combinatorics , mathematics , random graph , cardinality (data modeling) , matroid , enumeration , struct , weighting , discrete mathematics , hamiltonian path , randomized algorithm , hamiltonian (control theory) , graph , computer science , mathematical optimization , medicine , radiology , data mining , programming language
Let ℱ n be a family of subsets of {1,…, n }. We propose a simple randomized algorithm to estimate the cardinality of ℱ n from the maximum weight of a subset X ∈ℱ n in a random weighting of {1,…, n }. The examples include enumeration of perfect matchings in graphs, bases in matroids, and Hamiltonian cycles in graphs. © 1997 John Wiley & Sons, Inc. Random Struct. Alg. , 11 , 187–198 (1997)