4 papers
Approximating two-terminal network reliability
Weiming Feng, Yucheng Fu, Heng Guo
We present a fully polynomial-time randomised approximation scheme (FPRAS) for the two-terminal reliability problem on general graphs, both directed and undirected. We also show th…
Linear time approximation of the TV distance between product distributions
Konrad Anand, Alistair Benford, Heng Guo
The paper proposes a linear‑time algorithm that approximates the total variation distance between two product distributions.
Rapid mixing of the flip chain over non-crossing spanning trees
Konrad Anand, Weiming Feng, Graham Freifeld +3
We show that the flip chain for non-crossing spanning trees of points in convex position mixes in time . We use connections between Fuss-Catalan structures to c…
Sink-free orientations: a local sampler with applications
Konrad Anand, Graham Freifeld, Heng Guo +2
For sink-free orientations in graphs of minimum degree at least , we show that there is a deterministic approximate counting algorithm that runs in time $O((n^{73}/\varepsilon^{…