Speaker: Virginia Vassilevska
Time: Wednesday 12-1pm
Location: NSH 1507
Title: Models of Greedy Algorithms
Abstract:
In an attempt to define an abstract model that captures what we call
greedy algorithms, Borodin et al. define so called priority
algorithms, in the context of scheduling problems. Davis and
Impagliazzo further apply the framework to graph problems. A lot of
approximation lower bounds have been proven in this model. For
example, weighted vertex cover cannot be approximated by a better
factor than 2 using an algorithm fitting the framework. Furthermore,
most greedy algorithms seem to fit the framework - e.g. the greedy
weighted vertex cover algorithm.
The goal of the talk is to provide a brief survey on the research done on
priority algorithms.