Online, greedy, and conceptually simple algorithms

Allan Borodin, University of Toronto

What can and cannot be computed by “conceptually simple algorithms”? In this regard, my primary interest is in approximation algorithms for combinatorial optimization problems and the relation of such problems to areas such as scheduling, algorithmic game theory and computational social choice.

Why do we care about conceptual simplicity, and can we formalize such a concept? For some problems, simple algorithmic ideas provide the best-known solution or are reasonably competitive with the best-known algorithms, especially in the context of real data. Moreover, “in

practice”, it is often the case that users will opt for a quick understandable algorithm. While it is arguably impossible to precisely define a useful general definition of “simplicity”, we can study well-used (albeit rarely precisely defined) combinatorial algorithmic paradigms such as various forms and extensions of online and greedy algorithms, primal-dual algorithms, local search, and “simple” dynamic programming. Can we then provide definitions for such paradigms that are sufficiently expressive to capture many or most existing algorithms, but still allow us to prove impossibility results that do not rely on computational complexity assumptions? To what extent is our theoretical analysis consistent with performance in practice? We will consider the specific problem of online interval selection in different online settings. In particular, we will consider the problem in the random order arrival model when the online algorithm can permanently reject previously accepted intervals.