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}$.
• 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}$.