Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Near optimal online algorithms and fast approximation algorithms for resource allocation problems
Devanur N., Jain K., Sivan B., Wilkens C. Journal of the ACM66 (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?
yes
no
Other reviews under "Algorithm Design And Analysis": Date
Numerical recipes
Sprott J., Cambridge University Press, New York, NY, 1991. Type: Book (9780521406895)
Dec 1 1992
An interactive calculus theorem-prover for continuity properties
Suppes P., Takahashi S. Journal of Symbolic Computation 7(6): 573-590, 1989. Type: Article
Aug 1 1990
The numerical methods programming projects book
Grandine T., Oxford University Press, Inc., New York, NY, 1990. Type: Book (9789780198533870)
Mar 1 1991
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy