A new upper bound for \(( n , 3)\)-MAX-SAT

DOI10.1007/s10958-012-1101-zzbMath1261.68068MaRDI QIDQ1946835

Ivan A. Bliznets

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

zbMATH Keywords

upper bound; MAX-SAT; maximum satisdiability problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

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