The Moser--Tardos Framework with Partial Resampling

The resampling algorithm of Moser and Tardos is a powerful approach to develop constructive versions of the Lovász Local Lemma. We generalize this to partial resampling: When a bad event holds, we resample an appropriately random subset of the variables that define this event rather than the entire...

Full description

Saved in:
Bibliographic Details
Published in:Journal of the ACM 2019-09, Vol.66 (5), p.1-45
Main Authors: Harris, David G., Srinivasan, Aravind
Format: Article
Language:English
Subjects:
Algorithms
Random variables
Resampling
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The resampling algorithm of Moser and Tardos is a powerful approach to develop constructive versions of the Lovász Local Lemma. We generalize this to partial resampling: When a bad event holds, we resample an appropriately random subset of the variables that define this event rather than the entire set, as in Moser and Tardos. This is particularly useful when the bad events are determined by sums of random variables. This leads to several improved algorithmic applications in scheduling, graph transversals, packet routing, and so on. For instance, we settle a conjecture of Szabó and Tardos (2006) on graph transversals asymptotically and obtain improved approximation ratios for a packet routing problem of Leighton, Maggs, and Rao (1994).
ISSN:0004-5411
1557-735X
DOI:10.1145/3342222