Approximation algorithms for the maximum satisfiability problem

DOI10.1007/3-540-61422-2_124zbMATH Open0886.03033OpenAlexW1492679536MaRDI QIDQ4375642FDOQ4375642

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

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

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)

Cited In (30)

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

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)