On randomizing two derandomized greedy algorithms
Kevin Costello, A. Shapira, Prasad Tetali · Journal of Combinatorics · 2010
We consider the performance of two classic approximation algorithms which work by scanning the input and greedily constructing a solution.We investigate whether running these algorithms on a random permutation of the input can increase their performance ratio.We obtain the following results:1. Johnson's approximation algorithm for MAX-SAT is one of the first approximation algorithms to be rigorously analyzed.It has been shown that the performance ratio of this algorithm is 2/3.We show that when executed on a random permutation of the variables, the performance ratio of this algorithm is improved to 2/3 + c for some c > 0. This resolves an open problem of Chen, Friesen and Zhang [3].2. Motivated by the above improvement, we consider the performance of the greedy algorithm for MAX-CUT whose performance ratio is 1/2.Our hope was that running the greedy algorithm on a random permutation of the vertices would result in a 1/2 + c approximation algorithm.However, it turns out that in this case the performance of the algorithm remains 1/2.This resolves an open problem of Mathieu and Schudy [11].