Algorithms and Generalizations for the Lovasz Local Lemma
| dc.contributor.advisor | Srinivasan, Aravind | en_US |
| dc.contributor.author | Harris, David | en_US |
| dc.contributor.department | Applied Mathematics and Scientific Computation | en_US |
| dc.contributor.publisher | Digital Repository at the University of Maryland | en_US |
| dc.contributor.publisher | University of Maryland (College Park, Md.) | en_US |
| dc.date.accessioned | 2016-02-06T06:39:59Z | |
| dc.date.available | 2016-02-06T06:39:59Z | |
| dc.date.issued | 2015 | en_US |
| dc.description.abstract | The Lovasz Local Lemma (LLL) is a cornerstone principle of the probabilistic method for combinatorics. This shows that one can avoid a large of set of “bad-events” (forbidden configurations of variables), provided the local conditions are satisfied. The original probabilistic formulation of this principle did not give efficient algorithms. A breakthrough result of Moser & Tardos led to an framework based on resampling variables which turns nearly all applications of the LLL into efficient algorithms. We extend and generalize the algorithm of Moser & Tardos in a variety of ways. We show tighter bounds on the complexity of the Moser-Tardos algorithm, particularly its parallel form. We also give a new, faster parallel algorithm for the LLL. We show that in some cases, the Moser-Tardos algorithm can converge even thoughthe LLL itself does not apply; we give a new criterion (comparable to the LLL) for determining when this occurs. This leads to improved bounds for k-SAT and hypergraph coloring among other applications. We describe an extension of the Moser-Tardos algorithm based on partial resampling, and use this to obtain better bounds for problems involving sums of independent random variables, such as column-sparse packing and packet-routing. We describe a variant of the partial resampling algorithm specialized to approximating column-sparse covering integer programs, a generalization of set-cover. We also give hardness reductions and integrality gaps, showing that our partial resampling based algorithm obtains nearly optimal approximation factors. We give a variant of the Moser-Tardos algorithm for random permutations, one of the few cases of the LLL not covered by the original algorithm of Moser & Tardos. We use this to develop the first constructive algorithms for Latin transversals and hypergraph packing, including parallel algorithms. We analyze the distribution of variables induced by the Moser-Tardos algorithm. We show it has a random-like structure, which can be used to accelerate the Moser-Tardos algorithm itself as well as to cover problems such as MAX k-SAT in which we only partially avoid bad-events. | en_US |
| dc.identifier | https://doi.org/10.13016/M2213R | |
| dc.identifier.uri | http://hdl.handle.net/1903/17276 | |
| dc.language.iso | en | en_US |
| dc.subject.pqcontrolled | Theoretical mathematics | en_US |
| dc.subject.pqcontrolled | Computer science | en_US |
| dc.subject.pquncontrolled | Lovasz Local Lemma | en_US |
| dc.subject.pquncontrolled | Moser-Tardos Algorithm | en_US |
| dc.title | Algorithms and Generalizations for the Lovasz Local Lemma | en_US |
| dc.type | Dissertation | en_US |
Files
Original bundle
1 - 1 of 1