On Some Recent Approximation Algorithms for MAX SAT

DOI10.1007/978-3-642-54423-1_52MaRDI QIDQ5405076zbMATH OpenOpenAlexFDO

Authors Matthias Poloczek, David P. Williamson, Anke van Zuylen

Publication date 31 March 2014

Published in LATIN 2014: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-54423-1_52

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 1258327
• scientific article; zbMATH DE number 1552232
• Improved approximation algorithms for MAX SAT
• scientific article; zbMATH DE number 1445292
• scientific article; zbMATH DE number 1302170
• scientific article; zbMATH DE number 1002206
• Approximation algorithms for the maximum satisfiability problem
• Approximating MAX SAT by moderately exponential and parameterized algorithms
• Approximating MAX SAT by moderately exponential and parameterized algorithms

Cited in

(18)

• Sums of squares based approximation algorithms for MAX-SAT
• Approximating a generalization of MAX 2SAT and MIN 2SAT
• On the hardness of approximating max-satisfy
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• MAX SAT approximation beyond the limits of polynomial-time approximation
• scientific article; zbMATH DE number 1258327 (Why is no real title available?)
• Bounds on greedy algorithms for MAX SAT
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Simpler 3/4-approximation algorithms for MAX SAT
• Randomized variants of Johnson's algorithm for MAX SAT
• Simple approximation algorithms for balanced MAX~2SAT
• On Approximation Algorithms for Hierarchical MAX-SAT
• Randomized greedy: new variants of some classic approximation algorithms
• scientific article; zbMATH DE number 1552232 (Why is no real title available?)
• Approximating MAX SAT by moderately exponential and parameterized algorithms
• Simple Approximation Algorithms for Balanced MAX 2SAT
• An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
• Theory and Applications of Satisfiability Testing

This page was built for publication: On Some Recent Approximation Algorithms for MAX SAT

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