The probabilistic analysis of a greedy satisfiability algorithm

Alexis C. Kaporis; Lefteris M. Kirousis; Efthimios G. Lalas

doi:10.1007/3-540-45749-6_51

The probabilistic analysis of a greedy satisfiability algorithm

Alexis C. Kaporis, Lefteris M. Kirousis, Efthimios G. Lalas

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Consider the following simple, greedy Davis-Putnam algorithm applied to a random 3-CNF formula of constant density c: Arbitrarily set to TRUE a literal that appears in as many clauses as possible, irrespective of their size (and irrespective of the number of occurrences of the negation of the literal). Reduce the formula. If any unit clauses appear, then satisfy their literals arbitrarily, reducing the formula accordingly, until no unit clause remains. Repeat. We prove that for c< 3.42 a slight modification of this algorithm computes a satisfying truth assignment with probability asymptotically bounded away from zero. Previously, algorithms of increasing sophistication were shown to succeed for c< 3.26. Preliminary experiments we performed suggest that c≈3.6 is feasible running algorithms like the above, which take into account not only the number of occurrences of a literal but also the number of occurrences of its negation, irrespectively of clause-size information.

Original language	English (US)
Title of host publication	Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings
Editors	Rolf Möhring, Rajeev Raman
Publisher	Springer Verlag
Pages	574-586
Number of pages	13
ISBN (Electronic)	3540441808, 9783540441809
DOIs	https://doi.org/10.1007/3-540-45749-6_51
State	Published - 2002
Event	10th Annual European Symposium on Algorithms, ESA 2002 - Rome, Italy Duration: Sep 17 2002 → Sep 21 2002

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2461
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	10th Annual European Symposium on Algorithms, ESA 2002
Country/Territory	Italy
City	Rome
Period	9/17/02 → 9/21/02

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-45749-6_51

Cite this

Kaporis, A. C., Kirousis, L. M., & Lalas, E. G. (2002). The probabilistic analysis of a greedy satisfiability algorithm. In R. Möhring, & R. Raman (Eds.), Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings (pp. 574-586). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2461). Springer Verlag. https://doi.org/10.1007/3-540-45749-6_51

The probabilistic analysis of a greedy satisfiability algorithm. / Kaporis, Alexis C.; Kirousis, Lefteris M.; Lalas, Efthimios G.
Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings. ed. / Rolf Möhring; Rajeev Raman. Springer Verlag, 2002. p. 574-586 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2461).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kaporis, AC, Kirousis, LM & Lalas, EG 2002, The probabilistic analysis of a greedy satisfiability algorithm. in R Möhring & R Raman (eds), Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2461, Springer Verlag, pp. 574-586, 10th Annual European Symposium on Algorithms, ESA 2002, Rome, Italy, 9/17/02. https://doi.org/10.1007/3-540-45749-6_51

Kaporis AC, Kirousis LM, Lalas EG. The probabilistic analysis of a greedy satisfiability algorithm. In Möhring R, Raman R, editors, Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings. Springer Verlag. 2002. p. 574-586. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45749-6_51

Kaporis, Alexis C. ; Kirousis, Lefteris M. ; Lalas, Efthimios G. / The probabilistic analysis of a greedy satisfiability algorithm. Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings. editor / Rolf Möhring ; Rajeev Raman. Springer Verlag, 2002. pp. 574-586 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{df6d1102bebc4bc88c909ca9af800261,

title = "The probabilistic analysis of a greedy satisfiability algorithm",

abstract = "Consider the following simple, greedy Davis-Putnam algorithm applied to a random 3-CNF formula of constant density c: Arbitrarily set to TRUE a literal that appears in as many clauses as possible, irrespective of their size (and irrespective of the number of occurrences of the negation of the literal). Reduce the formula. If any unit clauses appear, then satisfy their literals arbitrarily, reducing the formula accordingly, until no unit clause remains. Repeat. We prove that for c< 3.42 a slight modification of this algorithm computes a satisfying truth assignment with probability asymptotically bounded away from zero. Previously, algorithms of increasing sophistication were shown to succeed for c< 3.26. Preliminary experiments we performed suggest that c≈3.6 is feasible running algorithms like the above, which take into account not only the number of occurrences of a literal but also the number of occurrences of its negation, irrespectively of clause-size information.",

author = "Kaporis, {Alexis C.} and Kirousis, {Lefteris M.} and Lalas, {Efthimios G.}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2002.; 10th Annual European Symposium on Algorithms, ESA 2002 ; Conference date: 17-09-2002 Through 21-09-2002",

year = "2002",

doi = "10.1007/3-540-45749-6_51",

language = "English (US)",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "574--586",

editor = "Rolf M{\"o}hring and Rajeev Raman",

booktitle = "Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings",

}

TY - GEN

T1 - The probabilistic analysis of a greedy satisfiability algorithm

AU - Kaporis, Alexis C.

AU - Kirousis, Lefteris M.

AU - Lalas, Efthimios G.

PY - 2002

Y1 - 2002

N2 - Consider the following simple, greedy Davis-Putnam algorithm applied to a random 3-CNF formula of constant density c: Arbitrarily set to TRUE a literal that appears in as many clauses as possible, irrespective of their size (and irrespective of the number of occurrences of the negation of the literal). Reduce the formula. If any unit clauses appear, then satisfy their literals arbitrarily, reducing the formula accordingly, until no unit clause remains. Repeat. We prove that for c< 3.42 a slight modification of this algorithm computes a satisfying truth assignment with probability asymptotically bounded away from zero. Previously, algorithms of increasing sophistication were shown to succeed for c< 3.26. Preliminary experiments we performed suggest that c≈3.6 is feasible running algorithms like the above, which take into account not only the number of occurrences of a literal but also the number of occurrences of its negation, irrespectively of clause-size information.

AB - Consider the following simple, greedy Davis-Putnam algorithm applied to a random 3-CNF formula of constant density c: Arbitrarily set to TRUE a literal that appears in as many clauses as possible, irrespective of their size (and irrespective of the number of occurrences of the negation of the literal). Reduce the formula. If any unit clauses appear, then satisfy their literals arbitrarily, reducing the formula accordingly, until no unit clause remains. Repeat. We prove that for c< 3.42 a slight modification of this algorithm computes a satisfying truth assignment with probability asymptotically bounded away from zero. Previously, algorithms of increasing sophistication were shown to succeed for c< 3.26. Preliminary experiments we performed suggest that c≈3.6 is feasible running algorithms like the above, which take into account not only the number of occurrences of a literal but also the number of occurrences of its negation, irrespectively of clause-size information.

UR - http://www.scopus.com/inward/record.url?scp=84938084560&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84938084560&partnerID=8YFLogxK

U2 - 10.1007/3-540-45749-6_51

DO - 10.1007/3-540-45749-6_51

M3 - Conference contribution

AN - SCOPUS:84938084560

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 574

EP - 586

BT - Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings

A2 - Möhring, Rolf

A2 - Raman, Rajeev

PB - Springer Verlag

T2 - 10th Annual European Symposium on Algorithms, ESA 2002

Y2 - 17 September 2002 through 21 September 2002

ER -

The probabilistic analysis of a greedy satisfiability algorithm

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this