Contents Online

# Journal of Combinatorics

## Volume 1 (2010)

### Number 3

### On randomizing two derandomized greedy algorithms

Pages: 265 – 283

DOI: http://dx.doi.org/10.4310/JOC.2010.v1.n3.a1

#### Authors

#### Abstract

We consider the performance of two classic approximation algorithmswhich work by scanning the input and greedily constructing a solution.We investigate whether running these algorithms on a random permutationof the input can increase their performance ratio. We obtain thefollowing results:

1. Johnson's approximation algorithm for MAX-SAT is one of the firstapproximation algorithms to be rigorously analyzed. It has been shownthat the performance ratio of this algorithm is 2/3. We show that whenexecuted on a random permutation of the variables, the performanceratio of this algorithm is improved to $2/3+c$ for some $c>0$. Thisresolves an open problem of Chen, Friesen and Zhang \cite{CFZ}.

2. Motivated by the above improvement, we consider the performance ofthe greedy algorithm for MAX-CUT whose performance ratio is 1/2. Ourhope was that running the greedy algorithm on a random permutation ofthe vertices would result in a $1/2+c$ approximation algorithm.However, it turns out that in this case the performance of thealgorithm remains 1/2. This resolves an open problem of Mathieu andSchudy.

#### Keywords

randomized algorithms, approximation algorithms, random graphs

#### 2010 Mathematics Subject Classification

Primary 68W20. Secondary 05C80, 68W25.