The Moser--Tardos Framework with Partial Resampling

DOI10.1145/3342222MaRDI QIDQ5215465zbMATHOpenAlexWikidataFDO

Authors David G. Harris, Aravind Srinivasan

Publication date 11 February 2020

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.5943

zbMATH Keywords

discrepancypacket routingindependent transversalresampling algorithmLovász local lemma

Mathematics Subject Classification ID

Combinatorial probability (60C05) Transversal (matching) theory (05D15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: The resampling algorithm of Moser & Tardos is a powerful approach to develop constructive versions of the Lov'{a}sz Local Lemma (LLL). 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 & 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 etc. For instance, we settle a conjecture of Szab'{o} & Tardos (2006) on graph transversals asymptotically, and obtain improved approximation ratios for a packet routing problem of Leighton, Maggs, & Rao (1994).

Recommendations

• The Moser-Tardos Resample algorithm: Where is the limit? (an experimental inquiry)
• Resampling method under dependent models
• A unified principled framework for resampling based on pseudo-populations: asymptotic theory
• Sampling moments of resamples
• Resampling estimation when observations are m–dependent
• Resampling Methods for Testing a Semiparametric Random Censorship Model
• A resampling method based on pivotal estimating functions
• Resampled regenerative estimators

Cited in

(12)

• Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel
• Tight bounds for online vector scheduling
• Distributed algorithms for the Lovász local lemma and graph coloring
• Fundamentals of partial rejection sampling
• Streaming algorithms for bin packing and vector scheduling
• New bounds for the Moser-Tardos distribution
• Coupled and \(k\)-sided placements: generalizing generalized assignment
• The Moser-Tardos Resample algorithm: Where is the limit? (an experimental inquiry)
• Finding independent transversals efficiently
• Commutative algorithms approximate the LLL-distribution
• Moser-Tardos resampling algorithm, entropy compression method and the subset gas
• Dynamic Sampling from Graphical Models

This page was built for publication: The Moser--Tardos Framework with Partial Resampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5215465)