Exact Algorithms for MAX-SAT

DOI10.1016/S1571-0661(04)80663-7zbMath1261.68073OpenAlexW1993837454MaRDI QIDQ4916231

Haiou Shen, Felip Manyà, Han-Tao 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

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

Related Items (6)

An efficient solver for weighted Max-SAT ⋮ MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability ⋮ On preprocessing for weighted MaxSAT ⋮ Efficient branch-and-bound algorithms for weighted MAX-2-SAT ⋮ Resolution for Max-SAT ⋮ An Empirical Study of MAX-2-SAT Phase Transitions

Uses Software

• MAX-2-SAT
• PBS

Cites Work

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

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