Premium
Tight bounds for popping algorithms
Author(s) -
Guo Heng,
He Kun
Publication year - 2020
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20928
Subject(s) - algorithm , sink (geography) , computer science , sampling (signal processing) , spanning tree , mathematics , combinatorics , cartography , filter (signal processing) , computer vision , geography
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.