On the Lower Bounds of Random Max 3 and 4-SAT
From MaRDI portal
Publication:4632196
DOI10.1007/978-3-319-39817-4_26zbMATH Open1475.68227OpenAlexW2477990906MaRDI QIDQ4632196FDOQ4632196
Authors: 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
Recommendations
- On the lower bounds of random Max 3 and 4-SAT
- A tighter upper bound for random MAX \(2\)-SAT
- Lower bounds for random 3-SAT via differential equations
- scientific article; zbMATH DE number 437557
- Lower and Upper Bounds for Random Mimimum Satisfiability Problem
- Bounding the unsatisfiability threshold of random 3-SAT
- Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
- Algorithms and Computation
- Probabilistic characterization of random Max \(r\)-Sat
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial probability (60C05) Computational aspects of satisfiability (68R07)
Cites Work
- Title not available (Why is that?)
- Some optimal inapproximability results
- Title not available (Why is that?)
- A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
- The threshold for random ๐-SAT is 2^{๐}log2-๐(๐)
- Title not available (Why is that?)
- A lower bound for the 4-satisfiability threshold
- On the maximum satisfiability of random formulas
- Title not available (Why is that?)
- 1.0957-Approximation Algorithm for Random MAX-3SAT
Cited In (5)
Uses Software
This page was built for publication: On the Lower Bounds of Random Max 3 and 4-SAT
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4632196)
