Bernoulli Factories for Flow-Based Polytopes
Rad Niazadeh, Renato Paes Leme, Jon Schneider · SIAM Journal on Discrete Mathematics · 2024
Abstract. We construct explicit combinatorial Bernoulli factories for the following class of flow-based polytopes: integral 0/1-polytopes defined by a set of network flow constraints. This generalizes the results of Niazadeh et al. (who constructed an explicit factory for the specific case of bipartite perfect matchings) and provides novel exact sampling procedures for sampling paths, circulations, and [Formula: see text]-flows. In the process, we uncover new connections to algebraic combinatorics.