The probabilistic analysis of a greedy satisfiability algorithm
Copyright policy )The probabilistic analysis of a greedy satisfiability algorithm
AbstractOn input a random 3‐CNF formula of clauses‐to‐variables ratior3applies 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 forr3< 3.42 this heuristic succeeds with probability asymptotically bounded away from zero. Previously, heuristics of increasing sophistication were shown to succeed forr3< 3.26. We improve up tor3< 3.52 by further exploiting the degree of the negation of the evaluated to True literal. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006
- University of Patras Greece
Combinatorial probability, Analysis of algorithms, Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Combinatorial probability, Analysis of algorithms, Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).73 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 1% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!