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:

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.


Comments are closed.

%d bloggers like this: