Near-linear time samplers for matroid independent sets with applications

Xiaoyu Chen, Heng Guo, Xinyuan Zhang +1

We give a $\tilde{O}(n)$ time almost uniform sampler for independent sets of a matroid, whose ground set has $n$ elements and is given by an independence oracle. As a consequen…