Greedy algorithms and why simple algorithms can be complex

by Allan Borodin

Oded's comments

Although this research agenda has been advocated by Allan for a while, I feel they did not receive enough attention, and wish to join Allan in advocating it. Allan quoted Karp saying that CS is the systematic study of algorithms, and rightfully argued that we should do a systematic study of "simple" (but very fast) algorithms. The tricky point is actually defining this term, and the papers surveyed by Allan do provide an excellent starting point.

The original abstract

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.


Back to list of Oded's choices.