We discuss a model of greedy algorithms. Many textbooks give examples of problems which can be solved either by greedy algorithms or algorithms using dynamic programming. To our knowledge this is the first attempt to formalize the limitations of greedy-like algorithms. We will discuss polynomially solvable problems from the scheduling world and show that these problems cannot be solved optimally by any greedy-like algorithm. We also discuss how well these problems can be approximated by a greedy algorithm.

Joint work with Allan Borodin and Charles Rackoff, both from the University of Toronto.

Host: Kim Skak Larsen