Journal
ACM TRANSACTIONS ON ALGORITHMS
Volume 13, Issue 4, Pages -Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3147211
Keywords
Lovasz Local Lemma; Shearer's criterion; Resampling Algorithm
Funding
- NSF [CCF-1527110, CCF-1618280, CNS-1010789, CCF-1422569]
Ask authors/readers for more resources
The Lovasz Local Lemma (LLL) is a cornerstone principle in the probabilistic method of combinatorics, and a seminal algorithm of Moser and Tardos (2010) provides an efficient randomized algorithm to implement it. This can be parallelized to give an algorithm that uses polynomially many processors and runs in O(log(3) n) time on an EREW PRAM, stemming from O(log n) adaptive computations of a maximal independent set (MIS). Chung et al. (2014) developed faster local and parallel algorithms, potentially running in time O(log(2) n), but these algorithms require more stringent conditions than the LLL. We give a new parallel algorithm that works under essentially the same conditions as the original algorithm of Moser and Tardos but uses only a single MIS computation, thus running in O(log(2) n) time on an EREW PRAM. This can be derandomized to give an NC algorithm running in time O(log(2) n) as well, speeding up a previous NC LLL algorithm of Chandrasekaran et al. (2013). We also provide improved and tighter bounds on the runtimes of the sequential and parallel resampling-based algorithms originally developed by Moser and Tardos. These apply to any problem instance in which the tighter Shearer LLL criterion is satisfied.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available