A Local Lemma for Focused Stochastic Algorithms
From MaRDI portal
Publication:5242924
DOI10.1137/16M109332XzbMath1493.68395arXiv1809.01537WikidataQ124891048 ScholiaQ124891048MaRDI QIDQ5242924
Vladimir Kolmogorov, Fotis Iliopoulos, Demetrios Achlioptas
Publication date: 8 November 2019
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1809.01537
Combinatorial probability (60C05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)
Related Items
Efficiently list‐edge coloring multigraphs asymptotically optimally ⋮ Moser-Tardos resampling algorithm, entropy compression method and the subset gas
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved bounds on coloring of graphs
- Acyclic edge coloring through the Lovász local lemma
- Nonrepetitive colouring via entropy compression
- Lopsided Lovász Local lemma and Latin transversals
- On a problem of Spencer
- The list chromatic number of graphs with small clique number
- Acyclic edge-coloring using entropy compression
- Proceedings of the forty-third annual ACM symposium on Theory of computing
- Highly nonrepetitive sequences: Winning strategies from the local lemma
- An Improvement of the Lovász Local Lemma via Cluster Expansion
- Acyclic and oriented chromatic numbers of graphs
- Star coloring of graphs
- Random Walks That Find Perfect Objects and the Lovász Local Lemma
- An Extension of the Moser--Tardos Algorithmic Local Lemma
- A constructive proof of the general lovász local lemma
- Estimation of sparse hessian matrices and graph coloring problems
- A parallel algorithmic version of the local lemma
- Focused Stochastic Local Search and the Lovász Local Lemma
- The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices
- New approach to nonrepetitive sequences
- The Lovász Local Lemma – A Survey
- A constructive proof of the Lovász local lemma
- The Moser-Tardos Resample algorithm: Where is the limit? (an experimental inquiry)
- A constructive algorithm for the Lovász Local Lemma on permutations
- New Constructive Aspects of the Lovász Local Lemma