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.
No takes yet. Share an insight, caveat, or question.
Guo et al. (2020) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: