The probabilistic analysis of a greedy satisfiability algorithm | Zendy

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

AI Assistant Blog Pricing

Home ZAIA Blog

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research