Most Computer Science department teach an undergraduate course call something like Introduction to Algorithms or the Fundamentals of Algorithmics or the Design and Analysis of Algorithms (to plagiarize the titles of some well known texts). Some of these courses and texts often organize the material in terms of “Algorithmic Paradigms”, such as greedy algorithms, dynamic programming, local search, etc. We seem to be able to intuitively describe what we have in mind when we discuss these classes of algorithms but rarely (if ever) do we( or any of the standard texts) attempt to define precisely what we mean by greedy, or dynamic programming. I have often said “you’ll know one when you see one”.
But what if you want to say something like “This is a difficult optimization problem…in particular, there is no greedy algorithm that provides an optimal (or even good approximation) for this problem”. Clearly, a precise definition is required if we want to defend such a statement.
In a paper co-authored with Morten Nielson and Charles Rackoff, we proposed a definition for greedy and greedy-like approximation algorithms, called priority algorithms. We did so in the context of classical scheduling problems . We also claimed that our definition could be extended (or be the basis for an extension) to other problem domains. More recently, Spyros Angelopoulos and I have applied the priority algorithm framework to the facility location and set cover problems. Russel Impagliazzo and Shaska Davis have also applied the framework to a number of traditional graph theoretic optimization problems.
Similar to the study of online algorithms, we are able to derive limitations on the (approximation) power of priority algorithms based only on the structure of the algorithm (allowing unbounded time complexity). In this talk, I will try to motivate the priority algorithm framework by discussing some well known greedy (or greedy-like) algorithms and the corresponding lower bounds we can prove within our framework. I will also mention some of the numerous open questions in this line of research.