Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems

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, display-ads problem for webpage banner-advertisement, 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 1-1/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 near-linear time algorithm to approximately solve very large LPs with both packing and covering constraints.

Joint work with Nikhil Devanur, Kamal Jain and Chris Wilkens