Focused stochastic local search and the Lovász local lemma

DOI10.1137/1.9781611974331.CH141MaRDI QIDQ4575726zbMATH OpenOpenAlexFDO

Authors Fotis Iliopoulos, D. Achlioptas

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.07633

Mathematics Subject Classification ID

Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorial probability (60C05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms (68W40)

Abstract: We develop tools for analyzing focused stochastic local search algorithms. These are algorithms which search a state space probabilistically by repeatedly selecting a constraint that is violated in the current state and moving to a random nearby state which, hopefully, addresses the violation without introducing many new ones. A large class of such algorithms arise from the algorithmization of the Lov'asz Local Lemma, a non-constructive tool for proving the existence of satisfying states. Here we give tools that provide a unified analysis of such algorithms and of many more, expressing them as instances of a general framework.

Recommendations

• A local lemma for focused stochastic algorithms
• A constructive proof of the Lovász local lemma
• Deterministic algorithms for the Lovász local lemma
• Deterministic algorithms for the Lovász local lemma
• scientific article; zbMATH DE number 1775440

Cited in

(8)

• The list chromatic number of graphs with small clique number
• Rainbow Hamilton cycles and lopsidependency
• Commutativity in the Algorithmic Lovász Local Lemma
• An algorithmic proof of the Lovász local lemma via resampling oracles
• Commutative algorithms approximate the LLL-distribution
• Stochastic control via entropy compression
• A local lemma for focused stochastic algorithms
• On triangle-free list assignments

This page was built for publication: Focused stochastic local search and the Lovász local lemma

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575726)