scientific article; zbMATH DE number 1302170
In the maximum satisfiability (MAX-SAT) problem one is given a Boolean formula in conjunctive normal form, that is, as a conjunction of clauses, each clause being a disjunction. The task is then to find an assignment to the variables that satisfies the maximum number of clauses. If one associates a positive weight to each clause one obtains the weighted MAX-SAT (MAX W-SAT) problem; one is then to determine an assignment to the variables that maximizes the sum of the weights of the satisfied clauses. Algorithms for these problems are surveyed in this handbook chapter. Exact algorithms, approximation algorithms, and local search heuristics are considered; some theoretical results regarding these are also presented. As the title of the chapter indicates, results on approximation and local search algorithms are well covered, whereas exact algorithms are given a more cursory treatment. For the entire collection see [Zbl 0903.90001].
- Solving weighted MAX-SAT via global equilibrium search
- Using heuristics to find minimal unsatisfiable subformulas in satisfiability problems
- On the hardness of approximating max-satisfy
- Approximating minimal unsatisfiable subformulae by means of adaptive core search
- Worst-case study of local search for MAX-\(k\)-SAT.
- On exact selection of minimally unsatisfiable subformulae
- Maximum satisfiability: how good are tabu search and plateau moves in the worst-case?
- Approximating a generalization of MAX 2SAT and MIN 2SAT
- Improved exact algorithms for MAX-SAT
- Restoring satisfiability or maintaining unsatisfiability by finding small unsatisfiable subformulae
- A nonmonotone GRASP
- scientific article; zbMATH DE number 1258327 (Why is no real title available?)
- On Approximation Algorithms for Hierarchical MAX-SAT
- scientific article; zbMATH DE number 1552232 (Why is no real title available?)
- An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
- Approximating MAX SAT by moderately exponential and parameterized algorithms
- Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- On Some Recent Approximation Algorithms for MAX SAT
- Theory and Applications of Satisfiability Testing
- MAX SAT approximation beyond the limits of polynomial-time approximation
- Practical applications of the alternating cycle decomposition
- Algorithms for the maximum satisfiability problem
- Differential approximation of MIN SAT, MAX SAT and related problems
- Sums of squares based approximation algorithms for MAX-SAT
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4247437)
