A Local Lemma for Focused Stochastic Algorithms

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

zbMATH Keywords

stochastic local searchLovász local lemmaMoser-Tardos algorithm

Mathematics Subject Classification ID

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

• Walksat
• ChainSAT

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