Tight bounds for popping algorithms

DOI10.1002/RSA.20928MaRDI QIDQ5136919zbMATH OpenOpenAlexFDO

Authors Heng Guo, Kun He

Publication date 30 November 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1807.01680

zbMATH Keywords

cluster-popping algorithmnetwork reliabilityspanning-treesuniform sampling

Mathematics Subject Classification ID

Sampling theory, sample surveys (62D05) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Neural nets and related approaches to inference from stochastic processes (62M45) Pattern recognition, speech recognition (68T10)

Abstract: We sharpen run-time analysis for algorithms under the partial rejection sampling framework. Our method yields improved bounds for: the cluster-popping algorithm for approximating all-terminal network reliability; the cycle-popping algorithm for sampling rooted spanning trees; the sink-popping algorithm for sampling sink-free orientations. In all three applications, our bounds are not only tight in order, but also optimal in constants.

Recommendations

• scientific article; zbMATH DE number 7375995
• A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
• Uniform sampling through the Lovász local lemma
• Uniform sampling through the Lovász local lemma
• scientific article; zbMATH DE number 1490110

Cited in

(11)

• New bounds for the balloon popping problem
• New bounds for the balloon popping problem
• Approximately counting bases of bicircular matroids
• Dynamic Sampling from Graphical Models
• Perfect sampling from spatial mixing
• Fundamentals of partial rejection sampling
• An FPRAS for two terminal reliability in directed acyclic graphs
• Near-linear time samplers for matroid independent sets with applications
• Sparsification of the regularized magnetic Laplacian with multi-type spanning forests
• Parameter estimation for Gibbs distributions
• Sink-free orientations: a local sampler with applications

This page was built for publication: Tight bounds for popping algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136919)