And Lecture #6 references

Some references from class yesterday: a short-and-sweet analysis for Johnson’s algorithm for MAX-SAT satisfying clauses is by Engebretsen; this simplifies the original proof by Chen, Friesen and Zhang. Recall that this analysis is tight if you take the clauses and consider the variables in the order : we could break ties badly and set and get whereas OPT is .

While it would seem that we’ve done all we can with this algorithm, the latest SODA conference has two interesting papers on the subject:

• The paper Randomized greedy: new variants of some classic approximation algorithms by Costello, Shapira, Tetali, which shows that considering the variables in a random order in Johnson’s algorithm achieves a performance of for some constant .
• Another paper Randomized Variants of Johnson’s Algorithm for MAX SAT by Poloczek and Schnitger shows that this random order idea cannot achieve , sadly. However, they give a variant of Johnson’s algorithm that does get .

Several questions remain: can we pin down better the performance of Johnson’s algorithm using a random order? It would be interesting to understand these papers, and perhaps to simplify the algorithm or the analysis in the latter? Can it be viewed as implicitly solving a linear program?

Update: And here are some lecture notes for MAX-3-SAT from the previous time Avrim taught the course.

About these ads