A new upper bound for \(( n , 3)\)-MAX-SAT
From MaRDI portal
Publication:1946835
DOI10.1007/s10958-012-1101-zzbMath1261.68068MaRDI QIDQ1946835
Publication date: 9 April 2013
Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10958-012-1101-z
Related Items
An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses, A refined branching algorithm for the maximum satisfiability problem, Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment, Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms, Improved MaxSAT Algorithms for Instances of Degree 3
Cites Work
- Unnamed Item
- A simplified NP-complete MAXSAT problem
- A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
- A new algorithm for optimal 2-constraint satisfaction and its implications
- New Bounds for MAX-SAT by Clause Learning
- Parameterized and Exact Computation
- A full derandomization of schöning's k-SAT algorithm
- Guided Search and a Faster Deterministic Algorithm for 3-SAT
- Algorithms – ESA 2005
- 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
- Theory and Applications of Satisfiability Testing
- MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in $\mathcal{O}(2^n)$ Time