Exact algorithms for MAX-SAT

DOI10.1016/S1571-0661(04)80663-7MaRDI QIDQ4916231zbMATH OpenOpenAlexFDO

Authors Haiou Shen, Felip Manya, Hantao Zhang

Publication date 19 April 2013

Published in Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s1571-0661(04)80663-7

Mathematics Subject Classification ID

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

Recommendations

• New Upper Bounds for Maximum Satisfiability
• scientific article; zbMATH DE number 2086240
• Publication:4938646
• Improved exact algorithms for MAX-SAT
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.

Cites work

• A Computing Procedure for Quantification Theory
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• A machine program for theorem-proving
• A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
• Algorithms for the maximum satisfiability problem
• An Empirical Study of MAX-2-SAT Phase Transitions
• Faster exact algorithms for hard problems: A parameterized point of view
• scientific article; zbMATH DE number 1500507 (Why is no real title available?)
• scientific article; zbMATH DE number 1522934 (Why is no real title available?)
• scientific article; zbMATH DE number 956857 (Why is no real title available?)
• scientific article; zbMATH DE number 956866 (Why is no real title available?)
• New Upper Bounds for Maximum Satisfiability
• New worst-case upper bounds for SAT
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Solving propositional satisfiability problems
• Theory and Applications of Satisfiability Testing
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.

Cited in

(23)

• Resolution for Max-SAT
• A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• Improved exact algorithms for MAX-SAT
• A refined branching algorithm for the maximum satisfiability problem
• On preprocessing for weighted MaxSAT
• MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
• Exact MAX-2SAT solution via lift-and-project closure
• scientific article; zbMATH DE number 1629855 (Why is no real title available?)
• A simplified NP-complete MAXSAT problem
• scientific article; zbMATH DE number 2086240 (Why is no real title available?)
• Solving #SAT and MAXSAT by Dynamic Programming
• An Empirical Study of MAX-2-SAT Phase Transitions
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Local maxima and improved exact algorithm for MAX-2-SAT
• Efficient branch-and-bound algorithms for weighted 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
• A Complete Calculus for Max-SAT
• Algorithms and Computation
• A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
• Improving exact algorithms for MAX-2-SAT
• An efficient solver for weighted Max-SAT

Describes a project that uses

Uses Software

• MAX-2-SAT
• PBS

This page was built for publication: Exact algorithms for MAX-SAT

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