CATS-Nov-8-2013
Title[edit]
Partial Resampling in the Moser-Tardos Framework
Speaker[edit]
David Harris, University of Maryland
Abstract[edit]
The resampling algorithm of Moser & Tardos is a powerful approach to develop constructive 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 variables that define this event, rather than the entire set as in Moser & Tardos. This is particularly useful when the bad-events are sums of random variables; in that case, we can (in effect) drastically lower the inter-dependency of the bad-events. This leads to several improved algorithmic applications in scheduling, graph transversals, packet routing etc. As a motivating example, we discuss a packet-routing algorithm of Leighton, Maggs, Rao; we show that this approach leads to much better approximation guarantees for scheduling.
