DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE UNIVERSITY OF SOUTHERN DENMARK, ODENSE Limitations of Greedy Algorithms Morten Nyhave Nielsen IMADA University of Southern Denmark, Odense Tuesday, October 24, 2000, at 2:15 PM The Seminar Room 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