Tight bound on Johnson's algorithm for maximum satisfiability
From MaRDI portal
Recommendations
- Simplified tight analysis of Johnson's algorithm
- Probabilistic bounds and algorithms for the maximum satisfiability problem
- Randomized variants of Johnson's algorithm for MAX SAT
- Tight bounds on local search to approximate the maximum satisfiability problems
- Improved approximation algorithms for MAX SAT
Cites work
- Algorithms for the maximum satisfiability problem
- Approximating satisfiable satisfiability problems
- Approximation algorithms for combinatorial problems
- Complexity of Partial Satisfaction
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
- On Syntactic versus Computational Views of Approximability
- On the Approximation of Maximum Satisfiability
Cited in
(11)- On extensions of the deterministic online model for bipartite matching and max-sat
- A novel algorithm for Max Sat calling MOCE to order
- CHAMP: a multipass algorithm for Max Sat based on saver variables
- Sublinear-space approximation algorithms for Max r-SAT
- Local search to approximate MAX NAE-k-SAT tightly
- An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
- Approximating Max NAE-\(k\)-SAT by anonymous local search
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- Optimization with uniform size queries
- Randomized variants of Johnson's algorithm for MAX SAT
- Simplified tight analysis of Johnson's algorithm
This page was built for publication: Tight bound on Johnson's algorithm for maximum satisfiability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1307701)
