Online Strategies for Hard Optimization Problems in Graphs

Presented on 11 Jan at ICORES 2014

Keynote Lecturer: Marc Demange

Abstract: Online optimization deals with instances of problems that are incrementally revealed over time. One should take decisions as soon as data are presented without information about the future data. The objective is to design strategies with absolute performance guaranties on the quality of the online computed solution vs the best possible solution with complete information. Online optimization allows to address dynamic environments with continuous flow of data, in particular when it is hard to assign a relevant probability system on possible futures. This approach reveals to be particularly interesting nowadays as more and more applications request to take into account ongoing instantaneous data. From a theoretical perspective, the online framework allows to better understand how the solutions of a problem may be a affected by a lack of information. In some sense, this topic can be seen as a continuation of approximation theory. Many concepts of polynomial approximation, such as reductions, could still be transferred to the online case. We will discuss different examples in online graph optimization (notably online coloring and TSP) that illustrate the basis of online algorithms and emphasize some future plans of this topic.