University Professor, Allan Borodin,
University of Toronto
Title: Conceptually simple combinatorial algorithms
Throughout history, there has been an appreciation of the importance of simplicity in the arts and sciences. In the context of algorithm design, and in particular in approximation algorithms, social choice and algorithmic game theory, the importance of simplicity is currently very much in vogue. In joint work with Avner and others, we proposed and studied two models for basic combinatorial algorithmic paradigms, namely a simple form of dynamic programming and a simple form of primal dual algorithms. I will present some examples of a renewed interest in the design of \conceptually simple algorithms". In particular, I will revisit the pBT model we proposed for simple dynamic programming and how it applies to a new derandomization result of Buchbinder and Feldman.
Schedule (10am-12 noon):
10:00 AM: Coffee and Tea
10:30 AM - 11:30am: Lecture
11:30 AM: Light refreshments