Competitive Analysis of Online Algorithms

Lecture 1: Competitive Analysis of Online Algorithms I
Lecture 2: Competitive Analysis of Online Algorithms II 
 

This series of talks is part of the Algorithms and Uncertainty Boot Camp. Videos for each talk area will be available through the links above.

Speaker: Seffi Naor, Technion Israel Institute of Technology

The talk 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. Recently, the framework has been extended to the non-linear setting, e.g., convex objective functions and semidefinite programming. Another important technique is dual fitting which plays an important role in the design of online algorithms, in particular in network design and scheduling. The focus of the talk will be on developing the general methodology, as well as highlighting connections to other fields such as online learning.