Tight bounds for popping algorithms

Heng Guo; Kun He

doi:10.1002/rsa.20928

Tight bounds for popping algorithms

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	371–392
Number of pages	22
Journal	Random Structures and Algorithms
Volume	57
Issue number	2
Early online date	6 May 2020
DOIs	https://doi.org/10.1002/rsa.20928
Publication status	Published - 30 Sept 2020

Keywords / Materials (for Non-textual outputs)

lovasz local lemma
network reliability
spanning-trees
uniform sampling

Access to Document

10.1002/rsa.20928Licence: Creative Commons: Attribution (CC-BY)

PRS-TightAccepted author manuscript, 203 KBLicence: Creative Commons: Attribution (CC-BY)
Tight bounds_GUO_DOA30012020_VOR_CC-BYFinal published version, 532 KBLicence: Creative Commons: Attribution (CC-BY)

https://onlinelibrary.wiley.com/doi/full/10.1002/rsa.20928Licence: Creative Commons: Attribution (CC-BY)

Cite this

@article{891ba108fc0348bca16bc3720ccc8282,

title = "Tight bounds for popping algorithms",

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.",

keywords = "lovasz local lemma, network reliability, spanning-trees, uniform sampling",

author = "Heng Guo and Kun He",

year = "2020",

month = sep,

day = "30",

doi = "10.1002/rsa.20928",

language = "English",

volume = "57",

pages = "371–392",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "Wiley",

number = "2",

}

TY - JOUR

T1 - Tight bounds for popping algorithms

AU - Guo, Heng

AU - He, Kun

PY - 2020/9/30

Y1 - 2020/9/30

N2 - 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.

AB - 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.

KW - lovasz local lemma

KW - network reliability

KW - spanning-trees

KW - uniform sampling

U2 - 10.1002/rsa.20928

DO - 10.1002/rsa.20928

M3 - Article

SN - 1042-9832

VL - 57

SP - 371

EP - 392

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 2

ER -

Tight bounds for popping algorithms

Abstract

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Cite this