Groupe d’études et de recherche en analyse des décisions

Online Resource Allocation Problems

Patrick Jaillet MIT, États-Unis

Technological advances in computing, communication, and in multi-purpose sensing capabilities at any scales have the potential to radically transform key existing activities and processes within societal, economical, governmental, and individual domains, and, in some cases, allow the emergence of new ones. Concentrating on a series of specific applications where dynamic resource allocations arise naturally within these technological advances, we introduce several online problems and use tools from online optimization to analyze them.

In particular, in this talk, we first introduce specific applications dealing with (i) sponsored search auctions and online auctions; (ii) load balancing for content delivery networks; (iii) distributed caching problems; and (iv) on-demand video/movie requests. We then introduce generic online general assignment problems that capture many aspects of these new applications. The second part of the talk deals with the design and analysis of online algorithms for these problems. We introduce and analyze several online algorithms built from either greedy principles or from general primal dual principles.