Abstract
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.
The second session of this mini course will take place on Tuesday, August 23rd, 2016 11:00 am – 12:00 pm.