The Moser--Tardos Framework with Partial Resampling

DOI10.1145/3342222zbMATH Open1476.05197arXiv1406.5943OpenAlexW2969466987WikidataQ127355740 ScholiaQ127355740MaRDI QIDQ5215465FDOQ5215465

David G. Harris, Aravind Srinivasan

Publication date: 11 February 2020

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

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).

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)

Cited In (12)

• Partial Resampling to Approximate Covering Integer Programs
• New bounds for the Moser‐Tardos distribution
• Streaming algorithms for bin packing and vector scheduling
• Distributed algorithms for the Lovász local lemma and graph coloring
• Title not available (Why is that?)
• Coupled and \(k\)-sided placements: generalizing generalized assignment
• Dynamic Sampling from Graphical Models
• The Moser-Tardos Resample algorithm: Where is the limit? (an experimental inquiry)
• Tight Bounds for Online Vector Scheduling
• Moser-Tardos resampling algorithm, entropy compression method and the subset gas
• Finding independent transversals efficiently
• Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel

Recommendations

• A resampling method based on pivotal estimating functions 👍 👎
• Resampling Methods for Testing a Semiparametric Random Censorship Model 👍 👎
• Resampling method under dependent models 👍 👎
• A unified principled framework for resampling based on pseudo-populations: asymptotic theory 👍 👎
• Resampling estimation when observations are m–dependent 👍 👎
• Resampled Regenerative Estimators 👍 👎
• The Moser-Tardos Resample algorithm: Where is the limit? (an experimental inquiry) 👍 👎
• Title not available (Why is that?) 👍 👎

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)