Journal
2013 IEEE 54TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS)
Volume -, Issue -, Pages 469-478Publisher
IEEE
DOI: 10.1109/FOCS.2013.57
Keywords
-
Categories
Funding
- Division Of Computer and Network Systems
- Direct For Computer & Info Scie & Enginr [1010789] Funding Source: National Science Foundation
Ask authors/readers for more resources
The resampling algorithm of Moser & Tardos is a powerful approach to develop versions of the Lovasz Local Lemma. We develop a partial resampling approach motivated by this methodology: when a bad event holds, we resample an appropriately-random subset of the set of variables that define this event, rather than the entire set as in Moser & Tardos. This leads to several improved algorithmic applications in scheduling, graph transversals, packet routing etc. For instance, we improve the approximation ratio of a generalized D-dimensional scheduling problem studied by Azar & Epstein from O(D) to O(log D/log log D), and settle a conjecture of Szabo & Tardos on graph transversals asymptotically.
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