×

zbMATH — the first resource for mathematics

Randomised approximation of the number of bases. (English) Zbl 0862.05020
Bonin, Joseph E. (ed.) et al., Matroid theory. AMS-IMS-SIAM joint summer research conference on matroid theory, July 2–6, 1995, University of Washington, Seattle, WA, USA. Providence, RI: American Mathematical Society. Contemp. Math. 197, 371-376 (1996).
The exact enumeration of the number of bases of a matroid is known to be \(\#\)-hard and even a good approximation is impossible if deterministic methods can only be used. The authors show that a polynomial randomised approximation scheme exists for a large class of matroids.
For the entire collection see [Zbl 0852.00021].

MSC:
05B35 Combinatorial aspects of matroids and geometric lattices
PDF BibTeX XML Cite