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_9zbMATH Open1352.68107OpenAlexW1465199488MaRDI QIDQ2891341FDOQ2891341

Authors: 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

Recommendations

• New exact algorithms for the 2-constraint satisfaction problem
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• New Upper Bounds for Maximum Satisfiability
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• scientific article; zbMATH DE number 1500507

zbMATH Keywords

algorithmconstraint satisfactionsatisfiabilitymaximum 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)

Cites Work

• A new algorithm for optimal 2-constraint satisfaction and its implications
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• A new approach to proving upper bounds for MAX-2-SAT
• Improved exact algorithms for MAX-SAT
• An exact algorithm for MAX-CUT in sparse graphs
• New upper bounds for the problem of maximal satisfiability
• MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in $\mathcal{O}(2^n)$ Time
• Exact Max 2-Sat: Easier and Faster

Cited In (10)

• New exact algorithms for the 2-constraint satisfaction problem
• An experimental evaluation of semidefinite programming and spectral algorithms for max cut
• Local maxima and improved exact algorithm for MAX-2-SAT
• Optimal 2-constraint satisfaction via sum-product algorithms
• Average-Case Analysis for the MAX-2SAT Problem
• A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between
• A new upper bound for Max-2-SAT: A graph-theoretic approach
• An upper (lower) bound for Max (Min) CSP
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• A tighter upper bound for random MAX \(2\)-SAT

This page was built for publication: New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2891341)