License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.33
URN: urn:nbn:de:0030-drops-154662
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15466/
Li, Shibo ;
Scheder, Dominik
Impatient PPSZ - A Faster Algorithm for CSP
Abstract
PPSZ is the fastest known algorithm for (d,k)-CSP problems, for most values of d and k. It goes through the variables in random order and sets each variable randomly to one of the d colors, excluding those colors that can be ruled out by looking at few constraints at a time.
We propose and analyze a modification of PPSZ: whenever all but 2 colors can be ruled out for some variable, immediately set that variable randomly to one of the remaining colors. We show that our new "impatient PPSZ" outperforms PPSZ exponentially for all k and all d ≥ 3 on formulas with a unique satisfying assignment.
BibTeX - Entry
@InProceedings{li_et_al:LIPIcs.ISAAC.2021.33,
author = {Li, Shibo and Scheder, Dominik},
title = {{Impatient PPSZ - A Faster Algorithm for CSP}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {33:1--33:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-214-3},
ISSN = {1868-8969},
year = {2021},
volume = {212},
editor = {Ahn, Hee-Kap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15466},
URN = {urn:nbn:de:0030-drops-154662},
doi = {10.4230/LIPIcs.ISAAC.2021.33},
annote = {Keywords: Randomized algorithms, Constraint Satisfaction Problems, exponential-time algorithms}
}
|
Keywords: |
|
Randomized algorithms, Constraint Satisfaction Problems, exponential-time algorithms |
|
Collection: |
|
32nd International Symposium on Algorithms and Computation (ISAAC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
30.11.2021 |
