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

DOI10.1007/s10958-012-1101-zzbMath1261.68068OpenAlexW2009777252MaRDI 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 boundMAX-SATmaximum satisdiability problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Related Items (5)

Improved MaxSAT Algorithms for Instances of Degree 3 ⋮ Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms ⋮ Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment ⋮ An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses ⋮ A refined branching algorithm for the maximum satisfiability problem

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

This page was built for publication: A new upper bound for \(( n , 3)\)-MAX-SAT