Approximately counting bases of bicircular matroids
From MaRDI portal
Publication:4993123
DOI10.1017/S0963548320000292zbMath1504.68282arXiv1808.09548OpenAlexW2889326428MaRDI QIDQ4993123
Publication date: 15 June 2021
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1808.09548
Combinatorial aspects of matroids and geometric lattices (05B35) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items
Perfect sampling from spatial mixing, Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Two remarks concerning balanced matroids
- Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains
- On the number of bases of bicircular matroids
- Strong convergence and a game of numbers
- Counting bases of representable matroids
- Modified log-Sobolev inequalities for strongly log-concave distributions
- Approximation algorithms for the normalizing constant of Gibbs distributions
- Random curves on surfaces induced from the Laplacian determinant
- Learning about critical phenomena from scribbles and sandpiles
- Adaptive simulated annealing: A near-optimal connection between sampling and counting
- Matrix Generalizations of Some Theorems on Trees, Cycles and Cocycles in Graphs
- BICIRCULAR MATROIDS
- How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
- Tight bounds for popping algorithms
- Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid
- A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
- Uniform Sampling Through the Lovász Local Lemma
- Generalized loop‐erased random walks and approximate reachability
- Moser and tardos meet Lovász
- On the Complexity of Computing the Tutte Polynomial of Bicircular Matroids
- On the Number of Combinatorial Geometries
- Generating a random sink-free orientation in quadratic time
