This is the calendar of the weekly Seminar S (until summer 2016 we meet at 26-00 room 428, on Wednesdays at 14:00)

Next seminar: Wednesday May 25, 2016

Kim Thang Nguyen (Evry University)
Online Primal-Dual Algorithms with Configuration Linear Programs

Abstract: In the talk, we present a primal-dual approach based on configuration linear programs to design competitive online algorithms. Prior to our work, configuration linear programs have been considered only in offline setting and the main approaches are rounding techniques that have their limit due to the exponential size of configuration formulations. Instead, we consider a primal-dual approach that first consists to strengthen natural linear programs by introducing exponential number of variables and constraints to reduce the integrality gap. Then, at any time, the algorithm maintains a primal feasible solution and a dual feasible solution for exponential number of dual constraints. The dual feasibility is proved by the mean of a new notion, called smoothness. The smoothness notion also allows us to characterize the competitiveness of online algorithms in our approach. Building upon our approach, we present competitive algorithms for a generalized network design problem and a energy minimization scheduling problem. These problems capture several extensively studied ones, such as Cost Distance, Buy-at-Bulk, Energy Efficient Network Routing, etc. For these concrete problems, our algorithms are optimal (up to a constant factor) in online setting and also have the currently best approximation guarantees in offline setting.

Past seminars (Academic year 2015-2016)