Title: Introduction to Competitive Analysis of Online Algorithms via Linear Programming

Speaker: Professor Seffi Naor

The workshop will survey various applications of linear programming to the design and analysis of competitive online algorithms. A unified approach, based on the primal-dual method, is discussed for a wide range of online covering and packing problems, having various objective functions. This approach has lead to the resolution of several important open problems, as well as a simple alternative view and analysis of many previously suggested algorithms. The focus of the workshop will be on developing the general methodology, as well as highlighting connections to other fields.

Biography:
Seffi Naor is an ACM Fellow and Professor of Computer Science at the Technion, Israel Institute of Technology, where he has been on the faculty since 1991. Prior to that, he was a postdoctoral fellow at at Stanford University and the University of Southern California. During 1998-2000 he was a member of the technical staff at Bell Laboratories, Lucent Technologies. During 2005-2007, he was a visiting researcher at Microsoft Research. Over the years he has been a regular visitor at IBM Research, Bell Labs, and Microsoft Research.

Seffi Naor’s research interests are mainly in the design and analysis of efficient algorithms, in particular approximation algorithms for NP-Hard algorithms and online algorithms, algorithmic game theory, and complexity theory. He has published over 150 papers in top professional journals and conferences. He is currently on the editorial board of the ACM Transactions on Algorithms and ACM Books and has served as chair of the program committee for the 2022 ACM-SIAM Symposium on Discrete Algorithms.

Registrations essential: Book your place by clicking on this link
Light lunch will be provided after the event

WED 21 FEBRUARY 2024 10.00 – 12.00 (AEDT, Melbourne Time)