Speaker: Jaime Davila
 
Day:  Wednesday, 10/13/2004
Room: ITE 336
Time:  3:30pm-4:30pm 

Title: A Tight Analysis of the Greedy Algorithm for Set Cover
----------------------------------------------------------------------------

Abstract: In these talk it will be shown an improved bound for the
performance of the greedy algorithm for approximating set cover which
improves the classical harmonic upper bound of H(m). This will be done
by showing that the performance ratio is exactly ln m - ln ln m +
\theta(1), where the difference between the upper and lower bounds is
less than 1.1. 

Based on the paper "A tight analysis of the greedy algorithm for set
cover"  by Petr Slavik, STOC 96. 

back to CSE-TS page