On Some Recent Approximation Algorithms for MAX SAT

DOI10.1007/978-3-642-54423-1_52zbMATH Open1407.68553OpenAlexW171146502MaRDI QIDQ5405076FDOQ5405076

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

Recommendations

• scientific article; zbMATH DE number 1258327
• scientific article; zbMATH DE number 1552232
• Improved approximation algorithms for MAX SAT
• Publication:4952605
• 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

Mathematics Subject Classification ID

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

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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)