Approximately counting bases of bicircular matroids
arXiv:1808.09548 · doi:10.1017/S0963548320000292
Abstract
We give a fully polynomial-time randomised approximation scheme (FPRAS) for the number of bases in a bicircular matroids. This is a natural class of matroids for which counting bases exactly is #P-hard and yet approximate counting can be done efficiently.
arXiv commentv3: updated introduction and a slightly better run-time bound. v4: minor revisions; this version is accepted for publication in Combinatorics, Probability and Computing (CPC)
References in corpus (6)
- Elementary bounds on Poincare and log-Sobolev constants for decomposable Markov chains
- Random curves on surfaces induced from the Laplacian determinant
- Approximation algorithms for the normalizing constant of Gibbs distributions
- A polynomial-time approximation algorithm for all-terminal network reliability
- A Faster Approximation Algorithm for the Gibbs Partition Function
- Tight bounds for popping algorithms