Speaker: Matthias Ullrich Poloczek, Cornell University

Title: Simple Approximation Algorithms for MAX SAT

Abstract:

The maximum satisfiability problem (MAX SAT) is a fundamental problem in discrete optimization. Given a collection of clauses with non-negative weights, our goal is to find an assignment to the variables that satisfies clauses of maximum total weight. We present a simple randomized greedy algorithm that achieves a 3/4-approximation in expectation. In particular, its performance is comparable to Yannakakis' algorithm based on flows and LP (1994) or the LP-rounding algorithm of Goemans and Williamson (1994). Then we show how to obtain a simple deterministic algorithm with same approximation ratio along the same lines.

In the second part of the talk we explore the limitations of these algorithmic approaches usingthe model of priority algorithms of Borodin, Nielsen, and Rackoff (2003). Based on joint work with Georg Schnitger, David P. Williamson, and Anke van Zuylen.