On the Approximation of Maximum Satisfiability
From MaRDI portal
Recommendations
Cited in
(53)- A new bound for 3-satisfiable MaxSat and its algorithmic application
- A new bound for 3-satisfiable MaxSat and its algorithmic application
- Approximating a generalization of MAX 2SAT and MIN 2SAT
- Tight bound on Johnson's algorithm for maximum satisfiability
- A fixed point operator for the generalised maximum satisfiability problem
- Efficient branch-and-bound algorithms for weighted MAX-2-SAT
- Approximating maximum satisfiable subsystems of linear equations of bounded width
- Simplified tight analysis of Johnson's algorithm
- On the hardness of approximating max-satisfy
- Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
- Reactive local search techniques for the maximum k-conjunctive constraint satisfaction problem (MAX-k-CCSP)
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- MAX SAT approximation beyond the limits of polynomial-time approximation
- scientific article; zbMATH DE number 2080247 (Why is no real title available?)
- scientific article; zbMATH DE number 1258327 (Why is no real title available?)
- Locally consistent constraint satisfaction problems
- Pseudo-Boolean optimization
- A bounded approximation for the minimum cost 2-sat problem
- Simple approximation algorithms for balanced MAX~2SAT
- Worst-case study of local search for MAX-\(k\)-SAT.
- A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
- Alphabet indexing for approximating features of symbols
- Local search to approximate MAX NAE-k-SAT tightly
- An approximation algorithm for alphabet indexing problem
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Investigation of maximum and minimum satisfiability problems using \(L\)-partition
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
- On Approximation Algorithms for Hierarchical MAX-SAT
- On approximation algorithms for the minimum satisfiability problem
- An approximation algorithm for MAX 3-SAT
- Sublinear-space approximation algorithms for Max r-SAT
- A new upper bound for Max-2-SAT: A graph-theoretic approach
- scientific article; zbMATH DE number 1552232 (Why is no real title available?)
- Revisiting maximum satisfiability and related problems in data streams
- Approximating MAX SAT by moderately exponential and parameterized algorithms
- Max NP-completeness made easy
- On approximability of satisfiable k -CSPs: I
- Revisiting maximum satisfiability and related problems in data streams
- The complexity of approximating \(\mathrm{PSPACE}\)-complete problems for hierarchical specifications
- On the minimum satisfiability problem
- Query-guided maximum satisfiability
- Maximum Constraint Satisfaction on Diamonds
- Partial Satisfaction of k-Satisfiable Formulas
- The complexity and approximability of finding maximum feasible subsystems of linear relations
- Maximum satisfiability: how good are tabu search and plateau moves in the worst-case?
- CHAMP: a multipass algorithm for Max Sat based on saver variables
- Go-MOCE: greedy order method of conditional expectations for Max Sat
- scientific article; zbMATH DE number 6783493 (Why is no real title available?)
- Approximating Max NAE-\(k\)-SAT by anonymous local search
- Dealing with 4-variables by resolution: an improved MaxSAT algorithm
- Parameterized constraint satisfaction problems: a survey
- Using the method of conditional expectations to supply an improved starting point for CCLS
- On weighted vs unweighted versions of combinatorial optimization problems
This page was built for publication: On the Approximation of Maximum Satisfiability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4314502)
