Greedy algorithms and why simple algorithms can be complex
Allan Borodin (University of Toronto, Canada)
While there has been a rich and ongoing development of new and often surprising algorithms in diverse areas, conceptually simple algorithms are often used for expediency and sometimes even to obtain the best known results for many fundamental problems. An ambitious (or perhaps naive) goal is to develop a theory for ``conceptually simple combinatorial algorithms'', starting off with greedy or myopic algorithms. I will review some of the (extensive) history of previous work in this regard, some recent ideas and results, and my current thinking about the power and (provable) limitations of simple algorithmic paradigms. In particular, I will present the priority algorithm framework as a model for greedy-like optimization algorithms. This model is also a good starting point for other simple algorithmic frameworks.