Georgia Institute of Technology College of Sciences

Many of the simplest and easiest implemented approximation algorithms can be thought of as derandomizations of the naive random algorithm.  Here we consider the question of whether performing the algorithm on a random reordering of the variables provides an improvement in the worst case expected performance. (1) For Johnson's algorithm for Maximum Satisfiability, we show this is indeed the case: While in the worst case Johnson's algorithm only provides a 2/3 approximation, the additional randomization step guarantees a 2/3+c approximation for some positive c. (2) For the greedy algorithm for MAX-CUT, we show to the contrary that the randomized version does NOT provide a 1/2+c approximation for any c on general graphs. This is in contrast to a result of Mathieu and Schudy showing it provides a 1-epsilon approximation on dense graphs. Joint with Asaf Shapira and Prasad Tetali.