Tight bound on Johnson's algorithm for maximum satisfiability

DOI10.1006/jcss.1998.1612zbMath0939.68165OpenAlexW2153838160MaRDI QIDQ1307701

Donald K. Friesen, Hao Zheng, Jian'er Chen

Publication date: 9 November 1999

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/f7d3ed8e002f6b407407f438aa68daa3cf4116cc

zbMATH Keywords

maximum satisfiability problem

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (10)

Simplified tight analysis of Johnson's algorithm ⋮ Local Search to Approximate Max NAE-$$k$$-Sat Tightly ⋮ A novel algorithm for Max Sat calling MOCE to order ⋮ An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem ⋮ CHAMP: a multipass algorithm for Max Sat based on saver variables ⋮ Sublinear-space approximation algorithms for Max \(r\)-SAT ⋮ On extensions of the deterministic online model for bipartite matching and max-sat ⋮ Approximating Max NAE-\(k\)-SAT by anonymous local search ⋮ Optimization with uniform size queries ⋮ Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds

Cites Work

• Unnamed Item
• Algorithms for the maximum satisfiability problem
• Approximation algorithms for combinatorial problems
• Approximating satisfiable satisfiability problems
• Complexity of Partial Satisfaction
• On Syntactic versus Computational Views of Approximability
• On the Approximation of Maximum Satisfiability
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

This page was built for publication: Tight bound on Johnson's algorithm for maximum satisfiability