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.