---
_id: '7412'
abstract:
- lang: eng
text: We develop a framework for the rigorous analysis of focused stochastic local
search algorithms. These algorithms 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 (we hope) not introducing many new violations.
An important class of focused local search algorithms with provable performance
guarantees has recently arisen from algorithmizations of the Lovász local lemma
(LLL), a nonconstructive 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 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 algorithm of
such type 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.
article_processing_charge: No
article_type: original
author:
- first_name: Dimitris
full_name: Achlioptas, Dimitris
last_name: Achlioptas
- first_name: Fotis
full_name: Iliopoulos, Fotis
last_name: Iliopoulos
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: Achlioptas D, Iliopoulos F, Kolmogorov V. A local lemma for focused stochastical
algorithms. SIAM Journal on Computing. 2019;48(5):1583-1602. doi:10.1137/16m109332x
apa: Achlioptas, D., Iliopoulos, F., & Kolmogorov, V. (2019). A local lemma
for focused stochastical algorithms. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/16m109332x
chicago: Achlioptas, Dimitris, Fotis Iliopoulos, and Vladimir Kolmogorov. “A Local
Lemma for Focused Stochastical Algorithms.” SIAM Journal on Computing.
SIAM, 2019. https://doi.org/10.1137/16m109332x.
ieee: D. Achlioptas, F. Iliopoulos, and V. Kolmogorov, “A local lemma for focused
stochastical algorithms,” SIAM Journal on Computing, vol. 48, no. 5. SIAM,
pp. 1583–1602, 2019.
ista: Achlioptas D, Iliopoulos F, Kolmogorov V. 2019. A local lemma for focused
stochastical algorithms. SIAM Journal on Computing. 48(5), 1583–1602.
mla: Achlioptas, Dimitris, et al. “A Local Lemma for Focused Stochastical Algorithms.”
SIAM Journal on Computing, vol. 48, no. 5, SIAM, 2019, pp. 1583–602, doi:10.1137/16m109332x.
short: D. Achlioptas, F. Iliopoulos, V. Kolmogorov, SIAM Journal on Computing 48
(2019) 1583–1602.
date_created: 2020-01-30T09:27:32Z
date_published: 2019-10-31T00:00:00Z
date_updated: 2023-09-06T15:25:29Z
day: '31'
department:
- _id: VlKo
doi: 10.1137/16m109332x
ec_funded: 1
external_id:
arxiv:
- '1809.01537'
isi:
- '000493900200005'
intvolume: ' 48'
isi: 1
issue: '5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1809.01537
month: '10'
oa: 1
oa_version: Preprint
page: 1583-1602
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: SIAM Journal on Computing
publication_identifier:
eissn:
- 1095-7111
issn:
- 0097-5397
publication_status: published
publisher: SIAM
quality_controlled: '1'
scopus_import: '1'
status: public
title: A local lemma for focused stochastical algorithms
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 48
year: '2019'
...