We define a class of matroids A for which a fully polynomial randomized approximation scheme (fpras) exists for counting the number of bases of the matroids. We then show that as the number of elements in a matroid increases, the probability that a matroid belongs to A goes to 1. We thus provide a fpras for counting the number of bases that applies to almost all matroids.
Citation: Congressus Numerantium
Pub Type: Journals
matroids, randomized algorithms