2 Search Results for "Moser, Robin A."


Document
Impatient PPSZ - A Faster Algorithm for CSP

Authors: Shibo Li and Dominik Scheder

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)


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.

Cite as

Shibo Li and Dominik Scheder. Impatient PPSZ - A Faster Algorithm for CSP. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 33:1-33:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.33},
  URN =		{urn:nbn:de:0030-drops-154662},
  doi =		{10.4230/LIPIcs.ISAAC.2021.33},
  annote =	{Keywords: Randomized algorithms, Constraint Satisfaction Problems, exponential-time algorithms}
}
Document
Improving PPSZ for 3-SAT using Critical Variables

Authors: Timon Hertli, Robin A. Moser, and Dominik Scheder

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)


Abstract
A critical variable of a satisfiable CNF formula is a variable that has the same value in all satisfying assignments. Using a simple case distinction on the fraction of critical variables of a CNF formula, we improve the running time for 3-SAT from O(1.32216^n) [Rolf 2006] to O(1.32153^n). Using a different approach, Iwama et al. very recently achieved a running time of O(1.32113^n). Our method nicely combines with theirs, yielding the currently fastest known algorithm with running time O(1.32065^n). We also improve the bound for 4-SAT from O(1.47390^n) [Hofmeister et al. 2002] to O(1.46928^n), where O(1.46981^n) can be obtained using the methods of Hofmeister and Rolf.

Cite as

Timon Hertli, Robin A. Moser, and Dominik Scheder. Improving PPSZ for 3-SAT using Critical Variables. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 237-248, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{hertli_et_al:LIPIcs.STACS.2011.237,
  author =	{Hertli, Timon and Moser, Robin A. and Scheder, Dominik},
  title =	{{Improving PPSZ for 3-SAT using Critical Variables}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{237--248},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.237},
  URN =		{urn:nbn:de:0030-drops-30147},
  doi =		{10.4230/LIPIcs.STACS.2011.237},
  annote =	{Keywords: SAT, satisfiability, randomized, exponential time, algorithm, 3-SAT, 4-SAT}
}
  • Refine by Author
  • 2 Scheder, Dominik
  • 1 Hertli, Timon
  • 1 Li, Shibo
  • 1 Moser, Robin A.

  • Refine by Classification
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 3-SAT
  • 1 4-SAT
  • 1 Constraint Satisfaction Problems
  • 1 Randomized algorithms
  • 1 SAT
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2011
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail