On the lower bounds of random Max 3 and 4-SAT

DOI10.1007/s10878-018-0267-9zbMath1417.90133OpenAlexW2787931001MaRDI QIDQ1752631

Guangyan Zhou, Zong Sheng Gao

Publication date: 24 May 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-018-0267-9

zbMATH Keywords

maximum satisfiabilitysecond moment methodweighting scheme

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (1)

Lower and Upper Bounds for Random Mimimum Satisfiability Problem

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
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• A lower bound for the 4-satisfiability threshold
• Some optimal inapproximability results
• The probabilistic analysis of a greedy satisfiability algorithm

This page was built for publication: On the lower bounds of random Max 3 and 4-SAT