# CMU Randomized Algorithms

Randomized Algorithms, Carnegie Mellon: Spring 2011

## And Lecture #6 references

Some references from class yesterday: a short-and-sweet analysis for Johnson’s algorithm for MAX-SAT satisfying ${(m + OPT)/3 \geq 2OPT/3}$ 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 ${(x_1 \lor x_2), (x_1 \lor x_3), (\lnot x_1)}$ and consider the variables in the order ${x_1, x_2, x_3}$: we could break ties badly and set ${x_1 = 1}$ and get ${2}$ whereas OPT is ${3}$.

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 ${(2/3 + \epsilon)OPT}$ for some constant ${\epsilon > 0}$.
• Another paper Randomized Variants of Johnson’s Algorithm for MAX SAT by Poloczek and Schnitger shows that this random order idea cannot achieve ${0.75}$, sadly. However, they give a variant of Johnson’s algorithm that does get ${0.75 OPT}$.

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.