Approximating highly satisfiable random 2-SAT

DOI10.1007/978-3-319-09284-3_28MaRDI QIDQ3192084zbMATH OpenOpenAlexFDO

Authors Andrei A. Bulatov, Cong Wang

Publication date 26 September 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-09284-3_28

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• On the maximum satisfiability of random formulas
• A remark on random 2-SAT
• Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
• Certifying unsatisfiability of random 2k-SAT formulas using approximation techniques.
• The number of satisfying assignments of random 2‐SAT formulas

Cited in

(4)

• Average-Case Analysis for the MAX-2SAT Problem
• Random 2-SAT: Results and problems
• The number of satisfying assignments of random 2‐SAT formulas
• Average-case analysis for the MAX-2SAT problem

This page was built for publication: Approximating highly satisfiable random 2-SAT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3192084)