On the Lower Bounds of Random Max 3 and 4-SAT

DOI10.1007/978-3-319-39817-4_26zbMath1475.68227OpenAlexW2477990906MaRDI QIDQ4632196

Guangyan Zhou

Publication date: 26 April 2019

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-39817-4_26

zbMATH Keywords

maximum satisfiabilityweighting schemesecond-moment method

Mathematics Subject Classification ID

Combinatorial probability (60C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)

Uses Software

• MAX-2-SAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
• On the maximum satisfiability of random formulas
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• 1.0957-Approximation Algorithm for Random MAX-3SAT
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• A lower bound for the 4-satisfiability threshold
• Some optimal inapproximability results

This page was built for publication: On the Lower Bounds of Random Max 3 and 4-SAT