A local lemma for focused stochastic algorithms
From MaRDI portal
Abstract: We develop a framework for the rigorous analysis of focused stochastic local search algorithms. These are algorithms that search a state space by repeatedly selecting some constraint that is violated in the current state and moving to a random nearby state that addresses the violation, while hopefully not introducing many new ones. An important class of focused local search algorithms with provable performance guarantees has recently arisen from algorithmizations of the Lov'{a}sz Local Lemma (LLL), a non-constructive tool for proving the existence of satisfying states by introducing a background measure on the state space. While powerful, the state transitions of algorithms in this class must be, in a precise sense, perfectly compatible with the background measure. In many applications this is a very restrictive requirement and one needs to step outside the class. Here we introduce the notion of emph{measure distortion} and develop a framework for analyzing arbitrary focused stochastic local search algorithms, recovering LLL algorithmizations as the special case of no distortion. Our framework takes as input an arbitrary such algorithm and an arbitrary probability measure and shows how to use the measure as a yardstick of algorithmic progress, even for algorithms designed independently of the measure.
Recommendations
Cites work
- A constructive algorithm for the Lovász local lemma on permutations
- A constructive proof of the general Lovász local lemma
- A constructive proof of the Lovász local lemma
- A parallel algorithmic version of the local lemma
- Acyclic and oriented chromatic numbers of graphs
- Acyclic edge coloring through the Lovász local lemma
- Acyclic edge-coloring using entropy compression
- An extension of the Moser-Tardos algorithmic local lemma
- An improvement of the Lovász local lemma via cluster expansion
- Estimation of sparse hessian matrices and graph coloring problems
- Focused stochastic local search and the Lovász local lemma
- Highly nonrepetitive sequences: winning strategies from the local Lemma
- scientific article; zbMATH DE number 1775440 (Why is no real title available?)
- scientific article; zbMATH DE number 956863 (Why is no real title available?)
- Improved bounds on coloring of graphs
- Lopsided Lovász Local lemma and Latin transversals
- New approach to nonrepetitive sequences
- New constructive aspects of the Lovász local lemma
- Nonrepetitive colouring via entropy compression
- On a problem of Spencer
- Proceedings of the 43rd annual ACM symposium on theory of computing, STOC '11. San Jose, CA, USA, June 6--8, 2011.
- Random walks that find perfect objects and the Lovász local lemma
- Series with central binomial coefficients, Catalan numbers, and harmonic numbers
- Star coloring of graphs
- The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices
- The list chromatic number of graphs with small clique number
- The Lovász Local Lemma – A Survey
- The Moser-Tardos Resample algorithm: Where is the limit? (an experimental inquiry)
Cited in
(6)- Moser-Tardos resampling algorithm, entropy compression method and the subset gas
- Focused stochastic local search and the Lovász local lemma
- Stochastic control via entropy compression
- Efficiently list‐edge coloring multigraphs asymptotically optimally
- A new notion of commutativity for the algorithmic Lovász local lemma
- Variable version Lovász local lemma: a tale of two boundaries
This page was built for publication: A local lemma for focused stochastic algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5242924)
