Premium
The probabilistic analysis of a greedy satisfiability algorithm
Author(s) -
Kaporis Alexis C.,
Kirousis Lefteris M.,
Lalas Efthimios G.
Publication year - 2006
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20104
Subject(s) - heuristics , negation , mathematics , literal (mathematical logic) , heuristic , satisfiability , probabilistic logic , discrete mathematics , bounded function , simple (philosophy) , combinatorics , set (abstract data type) , statement (logic) , algorithm , computer science , mathematical optimization , statistics , linguistics , programming language , mathematical analysis , philosophy , epistemology
On input a random 3‐CNF formula of clauses‐to‐variables ratio r 3 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 < 3.42 this heuristic succeeds with probability asymptotically bounded away from zero. Previously, heuristics of increasing sophistication were shown to succeed for r 3 < 3.26. We improve up to r 3 < 3.52 by further exploiting the degree of the negation of the evaluated to True literal. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006