New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree

DOI10.1007/978-3-642-28050-4_9zbMath1352.68107OpenAlexW1465199488MaRDI QIDQ2891341

Alexander Golovnev

Publication date: 15 June 2012

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-28050-4_9

zbMATH Keywords

algorithmsatisfiabilityconstraint satisfactionmaximum satisfiabilitymaximum constraint satisfaction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

New exact algorithms for the 2-constraint satisfaction problem ⋮ A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP

Cites Work

• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Improved exact algorithms for MAX-SAT
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• An exact algorithm for MAX-CUT in sparse graphs
• A new algorithm for optimal 2-constraint satisfaction and its implications
• New upper bounds for the problem of maximal satisfiability
• A new approach to proving upper bounds for MAX-2-SAT
• Exact Max 2-Sat: Easier and Faster
• 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: New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree