New Bounds for MAX-SAT by Clause Learning

DOI10.1007/978-3-540-74510-5_21MaRDI QIDQ3499776zbMATH OpenOpenAlexFDO

Authors Konstantin Kutzkov, Alexander S. Kulikov

Publication date 3 June 2008

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74510-5_21

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational learning theory (68Q32) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Boosting branch-and-bound MaxSAT solvers with clause learning
• Publication:4938646
• New Upper Bounds for Maximum Satisfiability
• New upper bounds for the problem of maximal satisfiability
• MAX SAT approximation beyond the limits of polynomial-time approximation

Cited in

(12)

• A new upper bound for \(( n , 3)\)-MAX-SAT
• A refined branching algorithm for the maximum satisfiability problem
• Improved exact algorithms for mildly sparse instances of MAX SAT
• New upper bounds for the problem of maximal satisfiability
• Improved algorithms for sparse MAX-SAT and MAX-k-CSP
• 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
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• 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
• A new upper bound for Max-2-SAT: A graph-theoretic approach
• Solving sparse instances of Max SAT via width reduction and greedy restriction

Describes a project that uses

Uses Software

• MAX-2-SAT
• SATO
• Chaff

This page was built for publication: New Bounds for MAX-SAT by Clause Learning

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