On Some Recent MAX SAT Approximation Algorithms

Matthias Poloczek, David P. Williamson, Anke van Zuylen

Recently a number of randomized 3/4-approximation algorithms for MAX SAT have been proposed that all work in the same way: given a fixed ordering of the variables, the algorithm ma…