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
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- Algorithms for the maximum satisfiability problem
- Approximating satisfiable satisfiability problems
- Approximation algorithms for combinatorial problems
- Complexity of Partial Satisfaction
- 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)- Simplified tight analysis of Johnson's algorithm
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- On extensions of the deterministic online model for bipartite matching and max-sat
- Randomized variants of Johnson's algorithm for MAX SAT
- Local search to approximate MAX NAE-\(k\)-SAT tightly
- A novel algorithm for Max Sat calling MOCE to order
- Sublinear-space approximation algorithms for Max \(r\)-SAT
- An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
- CHAMP: a multipass algorithm for Max Sat based on saver variables
- Approximating Max NAE-\(k\)-SAT by anonymous local search
- Optimization with uniform size queries
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)
