An approximation algorithm for MAX 3-SAT

DOI10.1007/BFB0015420MaRDI QIDQ6487958zbMATH OpenFDO

Authors Takao Ono, Tomio Hirata, T. Asano

Publication date 21 March 2023

Full work available at URL https://doi.org/10.1007/BFB0015420

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Recommendations

• Improved approximation algorithms for MAX SAT
• Approximation algorithms for the maximum satisfiability problem
• scientific article; zbMATH DE number 1445292
• On the Approximation of Maximum Satisfiability
• scientific article; zbMATH DE number 1002206

Cites work

• .878-approximation algorithms for MAX CUT and MAX 2SAT
• Approximation algorithms for combinatorial problems
• Efficient probabilistically checkable proofs and applications to approximations
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem

Cited in

(11)

• MAX3SAT is exponentially hard to approximate if NP has positive dimension.
• Improved approximation algorithms for MAX SAT
• A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem
• Conditional Hardness of Approximating Satisfiable Max 3CSP-q
• scientific article; zbMATH DE number 1303558 (Why is no real title available?)
• On the Approximation of Maximum Satisfiability
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• The Approximability of Three-valued MAX CSP
• scientific article; zbMATH DE number 7650314 (Why is no real title available?)
• Approximation and Online Algorithms

This page was built for publication: An approximation algorithm for MAX 3-SAT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6487958)