| Title | : | Online, greedy and conceptually simple algorithms |
| Speaker | : | Prof. Allan Borodin (University of Toronto) |
| Details | : | Wed, 8 Jan, 2025 3:30 PM @ SSB 334 |
| Abstract: | : | What can and cannot be computed by “conceptually simple algorithms”? In this regard, my primary interest is on 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 provide definitions for such paradigms that are sufficiently expressive so as to capture many or most existing algorithms, but still allow us to prove impossibility results that do not rely on computational complexity assumptions? More generally, in addition to competitive and approximation ratios for online and greedy algorithms, we are led to consider additional criteria such as fairness in various applications. In some sense, conceptual simplicity is an aspect of “fairness”: If users do not understand the outcome of an algorithm, they may likely perceive it as unfair.
Brief Bio of the Speaker: Allan Borodin is a University Professor at the University of Toronto in the Department of Computer Science. He joined the University of Toronto in 1969 and was the chair of the Department 1980-1985. His research areas include computational complexity and algorithm analysis and design. He has been a visiting professor at Cornell, ETH-Zurich, University of Nice, Hebrew University, and the Weizmann Institute. He is a Fellow of the Royal Society of Canada, an ACM Fellow and a Member, Order of Canada. |
