MATH Seminar

Title: On randomizing two derandomized greedy algorithms
Seminar: Combinatorics
Speaker: Kevin Costello of The Georgia Institute of Technology
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2010-10-01 at 4:00PM
Venue: W306
Download Flyer
Abstract: 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, this indeed turns out to be 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, it turns out 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 Sc hudy showing it provides a 1-epsilon approximation on dense graphs.\\ \\ Joint with Asaf Shapira and Prasad Tetali.