The resource allocation problem is an age-old problem with a rich history. This paper revisits the resource allocation problem, albeit in a different setting, finding “a middle ground between worst-case and stochastic [analyses]”: the input here is drawn from an unknown distribution. This is interesting because: (a) the worst-case setting cannot yield anything beyond a 1 – 1/e competitive ratio; and (b) the stochastic setting gives very distribution dependent algorithms.
The authors present a number of important and useful algorithms by applying some simple yet sophisticated techniques. They first present near-optimal prior robust online algorithms for resource allocation problems. A significant achievement here is the improved bound for the bid to budget ratio (in the context of the well-studied adwords problem). Also notable is the introduction to the adversarial stochastic input model, where “the distribution from which the requests arrive [may] change over time.”
Next, the authors analyze a simple but popular greedy algorithm for the adwords problem: “Always match an incoming query to the advertiser that has the maximum effective bid (the minimum of bid and remaining budget) for that query.” This algorithm is shown to achieve an approximation factor of 1 - 1/e with unknown distributions and no assumption on the bid to budget ratio.
Finally, the authors present “fast approximation algorithms for a wide class of mixed packing and covering integer programs” inspired by a general class of problems “where the instances are too large to use traditional algorithms.”
The presented results allow for a number of interesting follow-up works. But perhaps more notable is the fact that the authors’ algorithm for the adversarial stochastic input model resulted in “a significant improvement in revenue” (approximately ten percent) when applied in the display advertising management system at Microsoft.