Approximation algorithms for the maximum satisfiability problem

DOI10.1007/3-540-61422-2_124MaRDI QIDQ4375642zbMATHOpenAlexFDO

Authors T. Asano, Takao Ono, Tomio Hirata

Publication date 2 March 1998

Published in Algorithm Theory — SWAT'96 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61422-2_124

zbMATH Keywords

approximation algorithmsmaximum satisfiability problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 1002206
• scientific article; zbMATH DE number 1372698
• Improved approximation algorithms for MAX SAT
• On the Approximation of Maximum Satisfiability
• Publication:4952605

Cited in

(30)

• Theory and Applications of Satisfiability Testing
• An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
• Tight approximation algorithms for maximum separable assignment problems
• scientific article; zbMATH DE number 1303558 (Why is no real title available?)
• Algorithms for the maximum satisfiability problem
• Approximation and Online Algorithms
• Complexity and Approximability of Parameterized MAX-CSPs
• scientific article; zbMATH DE number 1304324 (Why is no real title available?)
• Near-optimal algorithms for maximum constraint satisfaction problems
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• On the hardness of approximating max-satisfy
• NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT
• Simple Approximation Algorithms for Balanced MAX 2SAT
• On Some Recent Approximation Algorithms for MAX SAT
• The maximum feasible subset problem (maxFS) and applications
• scientific article; zbMATH DE number 2080247 (Why is no real title available?)
• scientific article; zbMATH DE number 1258327 (Why is no real title available?)
• scientific article; zbMATH DE number 6381632 (Why is no real title available?)
• An approximation algorithm for MAX 3-SAT
• Sums of squares based approximation algorithms for MAX-SAT
• Improved approximation algorithms for MAX SAT
• On Approximation Algorithms for Hierarchical MAX-SAT
• On the Approximation of Maximum Satisfiability
• scientific article; zbMATH DE number 1552232 (Why is no real title available?)
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• Approximating maximum satisfiable subsystems of linear equations of bounded width
• Approximation Algorithms for CSPs
• Approximation algorithms for the max-buying problem with limited supply
• Approximating MAX SAT by moderately exponential and parameterized algorithms
• scientific article; zbMATH DE number 1445292 (Why is no real title available?)

This page was built for publication: Approximation algorithms for the maximum satisfiability problem

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