search

Tight Bounds for Popping Algorithms

CategoryPublications 244

Authors: Heng Guo, Kun He

Published in: RANDOM STRUCTURES & ALGORITHMS

Date of Publication: May 6, 2020

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; and the sink‐popping algorithm for sampling sink‐free orientations. In all three applications, our bounds are not only tight in order, but also optimal in30 constants.

View Full Text

Keywords2020Big data analytics under constrained resourcesKun HeRANDOM STRUCTURES & ALGORITHMS Previous: Next: