Abstract:
Recently, the primal dual method has emerged as a key tool for designing competitive online algorithms.
In this talk we will describe the online primal dual method, discuss how it is applicable to several seemingly unrelated problems, and also describe a recent polylogarithmic competitive algorithm for the k-server problem inspired by the primal dual method.