标题： 无源定向：一种局部采样器及其应用 显示英文标题

标题： Sink-free orientations: a local sampler with applications

摘要： 对于最小度至少为$3$的图中的无源定向，我们证明存在一个确定性近似计数算法，其运行时间为$O((n^{73}/\varepsilon^{72})\log(n/\varepsilon))$，一个接近线性时间的采样算法，以及一个随机近似计数算法，其运行时间为$O((n/\varepsilon)^2\log(n/\varepsilon))$，其中$n$表示输入图的顶点数，$0<\varepsilon<1$是所需的精度。所有三个算法都基于在部分拒绝采样框架（Guo, Jerrum, and Liu, 2019）下对无源弹出方法（Cohn, Pemantle, and Propp, 2002）的局部实现。 显示英文摘要

摘要： For sink-free orientations in graphs of minimum degree at least $3$, we show that there is a deterministic approximate counting algorithm that runs in time $O((n^{73}/\varepsilon^{72})\log(n/\varepsilon))$, a near-linear time sampling algorithm, and a randomised approximate counting algorithm that runs in time $O((n/\varepsilon)^2\log(n/\varepsilon))$, where $n$ denotes the number of vertices of the input graph and $0<\varepsilon<1$ is the desired accuracy. All three algorithms are based on a local implementation of the sink popping method (Cohn, Pemantle, and Propp, 2002) under the partial rejection sampling framework (Guo, Jerrum, and Liu, 2019).