Tight bounds for popping algorithms. Issue 2 (6th May 2020)
- Record Type:
- Journal Article
- Title:
- Tight bounds for popping algorithms. Issue 2 (6th May 2020)
- Main Title:
- Tight bounds for popping algorithms
- Authors:
- Guo, Heng
He, Kun - Abstract:
- 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.
- Is Part Of:
- Random structures & algorithms. Volume 57:Issue 2(2020)
- Journal:
- Random structures & algorithms
- Issue:
- Volume 57:Issue 2(2020)
- Issue Display:
- Volume 57, Issue 2 (2020)
- Year:
- 2020
- Volume:
- 57
- Issue:
- 2
- Issue Sort Value:
- 2020-0057-0002-0000
- Page Start:
- 371
- Page End:
- 392
- Publication Date:
- 2020-05-06
- Subjects:
- lovasz local lemma -- network reliability -- spanning‐trees -- uniform sampling
Random graphs -- Periodicals
Mathematical analysis -- Periodicals
519 - Journal URLs:
- http://onlinelibrary.wiley.com/journal/10.1002/(ISSN)1098-2418 ↗
http://onlinelibrary.wiley.com/ ↗ - DOI:
- 10.1002/rsa.20928 ↗
- Languages:
- English
- ISSNs:
- 1042-9832
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 7254.411950
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 13559.xml