The probabilistic analysis of a greedy satisfiability algorithm

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

doi:10.1002/rsa.20104

The probabilistic analysis of a greedy satisfiability algorithm

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

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

On input a random 3-CNF formula of clauses-to-variables ratio r₃ applies repeatedly the following simple heuristic: Set to TRUE a literal that appears in the maximum number of clauses, irrespective of their size and the number of occurrences of the negation of the literal (ties are broken randomly; 1-clauses when they appear get priority). We prove that for r₃ < 3.42 this heuristic succeeds with probability asymptotically bounded away from zero. Previously, heuristics of increasing sophistication were shown to succeed for r₃ < 3.26. We improve up to r₃ < 3.52 by further exploitingthe degree of the negation of the evaluated to TRUE literal.

Original language	English (US)
Pages (from-to)	444-480
Number of pages	37
Journal	Random Structures and Algorithms
Volume	28
Issue number	4
DOIs	https://doi.org/10.1002/rsa.20104
State	Published - Jul 2006

ASJC Scopus subject areas

Software
General Mathematics
Computer Graphics and Computer-Aided Design
Applied Mathematics

Access to Document

10.1002/rsa.20104

Cite this

@article{5761c806a9654353a7d8c039e8bd0368,

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

abstract = "On input a random 3-CNF formula of clauses-to-variables ratio r3 applies repeatedly the following simple heuristic: Set to TRUE a literal that appears in the maximum number of clauses, irrespective of their size and the number of occurrences of the negation of the literal (ties are broken randomly; 1-clauses when they appear get priority). We prove that for r3 < 3.42 this heuristic succeeds with probability asymptotically bounded away from zero. Previously, heuristics of increasing sophistication were shown to succeed for r3 < 3.26. We improve up to r3 < 3.52 by further exploitingthe degree of the negation of the evaluated to TRUE literal.",

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

year = "2006",

month = jul,

doi = "10.1002/rsa.20104",

language = "English (US)",

volume = "28",

pages = "444--480",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "4",

}

TY - JOUR

T1 - The probabilistic analysis of a greedy satisfiability algorithm

AU - Kaporis, Alexis C.

AU - Kirousis, Lefteris M.

AU - Lalas, Efthimios G.

PY - 2006/7

Y1 - 2006/7

N2 - On input a random 3-CNF formula of clauses-to-variables ratio r3 applies repeatedly the following simple heuristic: Set to TRUE a literal that appears in the maximum number of clauses, irrespective of their size and the number of occurrences of the negation of the literal (ties are broken randomly; 1-clauses when they appear get priority). We prove that for r3 < 3.42 this heuristic succeeds with probability asymptotically bounded away from zero. Previously, heuristics of increasing sophistication were shown to succeed for r3 < 3.26. We improve up to r3 < 3.52 by further exploitingthe degree of the negation of the evaluated to TRUE literal.

AB - On input a random 3-CNF formula of clauses-to-variables ratio r3 applies repeatedly the following simple heuristic: Set to TRUE a literal that appears in the maximum number of clauses, irrespective of their size and the number of occurrences of the negation of the literal (ties are broken randomly; 1-clauses when they appear get priority). We prove that for r3 < 3.42 this heuristic succeeds with probability asymptotically bounded away from zero. Previously, heuristics of increasing sophistication were shown to succeed for r3 < 3.26. We improve up to r3 < 3.52 by further exploitingthe degree of the negation of the evaluated to TRUE literal.

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

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

U2 - 10.1002/rsa.20104

DO - 10.1002/rsa.20104

M3 - Article

AN - SCOPUS:33745697542

SN - 1042-9832

VL - 28

SP - 444

EP - 480

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 4

ER -

The probabilistic analysis of a greedy satisfiability algorithm

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this