New Constructive Aspects of the Lovász Local Lemma
From MaRDI portal
Publication:5395672
DOI10.1145/2049697.2049702zbMath1281.68228arXiv1001.1231OpenAlexW2072870176WikidataQ124812386 ScholiaQ124812386MaRDI QIDQ5395672
Barna Saha, Bernhard Haeupler, Aravind Srinivasan
Publication date: 17 February 2014
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1001.1231
Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (24)
Randomly coloring simple hypergraphs with fewer colors ⋮ Restricted max-min allocation: integrality gap and approximation algorithm ⋮ Unnamed Item ⋮ Counting Solutions to Random CNF Formulas ⋮ Multistage online maxmin allocation of indivisible entities ⋮ Efficiently list‐edge coloring multigraphs asymptotically optimally ⋮ Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel ⋮ Strong LP formulations for scheduling splittable jobs on unrelated machines ⋮ Online max-min fair allocation ⋮ Unnamed Item ⋮ New bounds for the Moser‐Tardos distribution ⋮ Acyclic edge-coloring using entropy compression ⋮ On the configuration-LP for scheduling on unrelated machines ⋮ Restricted Max-Min Fair Allocation ⋮ Nonrepetitive colouring via entropy compression ⋮ Unnamed Item ⋮ On \((1, \epsilon )\)-restricted max-min fair allocation problem ⋮ An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles ⋮ Distributed algorithms for the Lovász local lemma and graph coloring ⋮ Counting Hypergraph Colorings in the Local Lemma Regime ⋮ Lazy Local Search Meets Machine Scheduling ⋮ A Local Lemma for Focused Stochastic Algorithms ⋮ Dynamic Sampling from Graphical Models ⋮ Upper Bounds on the Size of Covering Arrays
This page was built for publication: New Constructive Aspects of the Lovász Local Lemma
