| 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: |
 Click here to retrieve PDF version of paper (101KB) |
