Why simple algorithms work surprisingly well online (!?)
Denis Pankratov - Concordia University
Feb. 20, 2026, 2:30 p.m. - Feb. 20, 2026, 1:30 p.m.
ENGMD 280
Hosted by: Robert Robere
Online algorithms must make irrevocable decisions without knowing the future, and their performance is traditionally measured via competitive analysis against an offline optimum. While sophisticated techniques often yield the best worst-case guarantees, many conceptually simple algorithms, such as Greedy and FirstFit, consistently perform remarkably well in theory and in practice in the online setting. In this talk, I will survey a line of work developing a theory of conceptually simple online algorithms across several domains. Time permitting, this may include online renting servers in the cloud problem, online graph problems, online computational geometry, and distributed exploration. I will present some analytical techniques for studying Greedy-type algorithms, show settings where simple algorithms match or outperform more complex ones, and highlight some unexpected results. The broader goal is to understand why simplicity works even when it shouldn't, and how we can systematically design and analyze simple online algorithms without sacrificing rigour or guarantees.
Denis Pankratov is an associate professor in the Department of Computer Science and Software Engineering in Concordia University. He works on theoretical aspects of computer science (such as algorithm design and analysis, as well as complexity theory), motivated by practical considerations. In practice, algorithms often outperform the worst-case theoretical guarantees. Some striking examples of this phenomenon include Boolean satisfiability and linear programming. At a high level, his research aims to narrow this gap in our understanding through an information-theoretic lens.
