NIST logo

Publication Citation: Approximating the Number of Bases for Almost All Matroids

NIST Authors in Bold

Author(s): Brian D. Cloteaux;
Title: Approximating the Number of Bases for Almost All Matroids
Published: February 01, 2011
Abstract: 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
Volume: 202
Pages: pp. 149 - 154
Keywords: matroids; randomized algorithms
Research Areas: Math
PDF version: PDF Document Click here to retrieve PDF version of paper (103KB)