On the greedy algorithm for satisfiability

DOI10.1016/0020-0190(92)90029-UzbMath0780.68062OpenAlexW2087662271MaRDI QIDQ1198012

Christos H. Papadimitriou, Elias Koutsoupias

Publication date: 16 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90029-u

zbMATH Keywords

greedy algorithmanalysis of algorithmsprobabilistic analysissatisfiabilityBoolean formulaconjunctive normal form

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05)

Related Items (15)

Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas ⋮ Local search algorithms for SAT: Worst-case analysis ⋮ Some properties of sets tractable under every polynomial-time computable distribution ⋮ A bright side of NP-hardness of interval computations: Interval heuristics applied to NP-problems ⋮ Abduction from logic programs: Semantics and complexity ⋮ Hard random 3-SAT problems and the Davis-Putnam procedure ⋮ Probabilistic analysis of local search and NP-completeness result for constraint satisfaction ⋮ An algorithm for locating propagation source in complex networks ⋮ The complexity of Boolean constraint satisfaction local search problems ⋮ UnitWalk: A new SAT solver that uses local search guided by unit clause elimination ⋮ A Theoretical Analysis of Search in GSAT ⋮ Complexity-theoretic models of phase transitions in search problems ⋮ Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems ⋮ A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search. ⋮ Solving non-uniform planted and filtered random SAT formulas greedily

Cites Work

• Unnamed Item
• A guided tour of Chernoff bounds
• Counting the number of solutions for instances of satisfiability

This page was built for publication: On the greedy algorithm for satisfiability