Title : Lagragian Duality in Online Scheduling.

Speaker  :  Nguyen Kim Thang

Abstract : In online algorithms, potential function method is extensively 
used for analyzing algorithms; however, they yields little insight on how
to construct potential functions and how to design algorithms 
for related problems. In the talk, we present a principled approach 
based on Lagrangian duality to study online scheduling problems 
that admit only non-linear or even non-convex formulations.
This approach is simple yet powerful and it is seemingly a right tool 
to study online problems. We illustrate the approach through an energy 
minimization problem.