On the problem of approximating the number of bases of a matroid

DOI10.1016/0020-0190(94)90037-XzbMath0803.68079OpenAlexW2030810720WikidataQ57401584 ScholiaQ57401584MaRDI QIDQ1321827

Andrei Z. Broder, Yossi Azar, Alan M. Frieze

Publication date: 26 May 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)90037-x

zbMATH Keywords

computational complexitymatroidsapproximate countingmatroid oracle algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

Quantum algorithms for learning hidden strings with applications to matroid problems, Some Problems on Approximate Counting in Graphs and Matroids, Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids

Cites Work

• Unnamed Item
• Unnamed Item
• A geometric inequality and the complexity of computing volume
• The asymptotic number of geometries
• The computational complexity of matroid properties
• A random polynomial-time algorithm for approximating the volume of convex bodies
• On the Number of Combinatorial Geometries