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_9MaRDI QIDQ2891341zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(10)

• New exact algorithms for the 2-constraint satisfaction problem
• An experimental evaluation of semidefinite programming and spectral algorithms for max cut
• Optimal 2-constraint satisfaction via sum-product algorithms
• Local maxima and improved exact algorithm for MAX-2-SAT
• Average-Case Analysis for the MAX-2SAT Problem
• A new upper bound for Max-2-SAT: A graph-theoretic approach
• A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between
• 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)