
Speaker Balu Sivan Affiliation University of WisconsinMadison Host Nikhil Devanur Rangarajan Duration 00:45:47 Date recorded 4 August 2011 We present algorithms for a class of problems called resource allocation problems, both in the online setting with stochastic input and in the offline setting. This class of problems contains many interesting special cases such as the Adwords problem for search queries, displayads problem for webpage banneradvertisement, online network routing, Bayesian combinatorial auctions, etc. In the online setting we introduce a new distributional model called the adversarial stochastic input model (asi), which is a generalization of the model where the input elements to the algorithm are drawn i.i.d from a distribution unknown to the algorithm designer. In asi model, the distributions can change over time too. In this model, we give a near optimal approximation algorithm for the resource allocation problem under mild assumptions about the input. Our proof technique, which is based on a broader interpretation of pessimistic estimators, also gives a very simple proof that the natural greedy algorithm for the adwords problem has a competitive ratio of 11/e in the i.i.d model with unknown distributions, and more generally in the asi model, with no assumptions at all about the input. In the offline setting we give a fast nearlinear time algorithm to approximately solve very large LPs with both packing and covering constraints. Joint work with Nikhil Devanur, Kamal Jain and Chris Wilkens
©2011 Microsoft Corporation. All rights reserved.
By the same speaker 