Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Near optimal online algorithms and fast approximation algorithms for resource allocation problems
Devanur N., Jain K., Sivan B., Wilkens C.  Journal of the ACM 66 (1): 1-41, 2019. Type: Article
Date Reviewed: Sep 21 2021

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.

Reviewer:  M. Sohel Rahman Review #: CR147359
Bookmark and Share
Algorithm Design And Analysis (G.4 ... )
General (F.0 )
Would you recommend this review?
Other reviews under "Algorithm Design And Analysis": Date
The algorithm design manual (3rd ed.)
Skiena S.,  Springer International Publishing, Cham, Switzerland, 2020. 793 pp. Type: Book (978-3-030542-55-9)
May 12 2021
 Introduction to distributed self-stabilizing algorithms
Altisen K., Devismes S., Dubois S., Petit F.,  Morgan&Claypool Publishers, San Rafael, CA, 2019. 166 pp. Type: Book (978-1-681735-36-8)
May 12 2020
Comparative study of computational algorithms for the Lasso with high-dimensional, highly correlated data
Kim B., Yu D., Won J.  Applied Intelligence 48(8): 1933-1952, 2018. Type: Article
Oct 24 2018

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2021 ThinkLoud, Inc.
Terms of Use
| Privacy Policy