On the lower bounds of random Max 3 and 4-SAT
From MaRDI portal
Publication:1752631
DOI10.1007/s10878-018-0267-9zbMath1417.90133OpenAlexW2787931001MaRDI QIDQ1752631
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
Related Items (1)
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