论文标题
基于流程的伯努利工厂
Bernoulli Factories for Flow-Based Polytopes
论文作者
论文摘要
我们为\ emph {基于流的polytopes}类构建明确的组合bernoulli工厂；由一组网络流程约束定义的积分0/1-PolyTopes。这概括了Niazadeh等人的结果。 （他为双方完美匹配的特定情况构建了一个明确的工厂），并为采样路径，流通和$ k $ flows提供了新颖的精确采样程序。在此过程中，我们发现了与代数组合学的新连接。
We construct explicit combinatorial Bernoulli factories for the class of \emph{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 $k$-flows. In the process, we uncover new connections to algebraic combinatorics.
