Journal of Combinatorics

Volume 1 (2010)

Number 3

On randomizing two derandomized greedy algorithms

Pages: 265 – 283

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

Authors

Kevin P. Costello (School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia, U.S.A.)

Asaf Shapira (School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia, U.S.A.)

Prasad Tetali (School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia, U.S.A.)

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.

Published 1 January 2010