Borodin, Allan (University of Toronto)

Purpose

This proposal concerns a number of different research areas. However, my recent research interests are often motivated by the question as to what can and cannot be computed by ``conceptually simple algorithms''. In this regard, my primary interest concerns conceptually simple approximation algorithms for combinatorial optimization problems. More specifically, I am studying various forms and extensions of online and greedy algorithms, primal dual algorithms, dynamic programming algorithms, local algorithms, and local search. And most recently, I have been concerned with domains where rather naive randomization can often outperform more ``principled'' and sophisticated deterministic algorithms. As examples, we can ask, what is the simplest deterministic one pass algorithm that can match or surpass the 3/4 approximation ratio achieved by various algorithms for the Max-Sat problem and the same question as to exceeding the 1-1/e approximation for online bipartite matching. In particular, I am studying parallel and multi-pass online and greedy algorithms. It has recently been shown that such algorithms can be sometimes be derived from randomized algorithms. However, so far there are only a couple of