The Moser--Tardos Framework with Partial Resampling

DOI10.1145/3342222zbMath1476.05197arXiv1406.5943OpenAlexW2969466987WikidataQ127355740 ScholiaQ127355740MaRDI QIDQ5215465

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

discrepancyLovász local lemmapacket routingindependent transversalresampling algorithm

Mathematics Subject Classification ID

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

Related Items (10)

Partial Resampling to Approximate Covering Integer Programs ⋮ Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel ⋮ Coupled and \(k\)-sided placements: generalizing generalized assignment ⋮ Unnamed Item ⋮ New bounds for the Moser‐Tardos distribution ⋮ Tight Bounds for Online Vector Scheduling ⋮ Streaming algorithms for bin packing and vector scheduling ⋮ Distributed algorithms for the Lovász local lemma and graph coloring ⋮ Finding independent transversals efficiently ⋮ Dynamic Sampling from Graphical Models

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