Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models

ABSTRACT

Motivated by Internet advertising applications, online allocation problems have been studied extensively in various adversarial and stochastic models. While the adversarial arrival models are too pessimistic, many of the stochastic (such as i.i.d or random-order) arrival models do not realistically capture uncertainty in predictions. A significant cause for such uncertainty is the presence of unpredictable traffic spikes, often due to breaking news or similar events. To address this issue, a simultaneous approximation framework has been proposed to develop algorithms that work well both in the adversarial and stochastic models; however, this framework does not enable algorithms that make good use of partially accurate forecasts when making online decisions. In this paper, we propose a robust online stochastic model that captures the nature of traffic spikes in online advertising. In our model, in addition to the stochastic input for which we have good forecasting, an unknown number of impressions arrive that are adversarially chosen.We design algorithms that combine an stochastic algorithm with an online algorithm that adaptively reacts to inaccurate predictions. We provide provable bounds for our new algorithms in this framework. We accompany our positive results with a set of hardness results showing that that our algorithms are not far from optimal in this framework. As a byproduct of our results, we also present improved online algorithms for a slight variant of the simultaneous approximation framework.

References

1. Agrawal, S., Wang, Z., and Ye, Y. 2009. A dynamic near-optimal algorithm for online linear programming. Computing Research Repository.
2. Alaei, S., Hajiaghayi, M., and Liaghat, V. 2012. Online prophet-inequality matching with applications to ad allocation. In Proceedings of the 13th ACM Conference on Electronic Commerce. ACM, 18--35.
3. Applegate, D. and Cohen, E. 2006. Making routing robust to changing traffic demands: algorithms and evaluation. IEEE/ACM Transactions on Networking (TON) 14, 6, 1193--1206.
4. Azar, Y., Cohen, E., Fiat, A., Kaplan, H., and Racke, H. 2003. Optimal oblivious routing in polynomial time. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing. ACM, 383--388.
5. Bahmani, B. and Kapralov, M. 2010. Improved bounds for online stochastic matching. In European Symposium on Algorithms. Springer, 170--181.
6. Ben-Tal, A. and Nemirovski, A. 2002. Robust optimization--methodology and applications. Mathematical Programming 92, 3, 453--480.
7. Bertsimas, D., Pachamanova, D., and Sim, M. 2004. Robust linear optimization under general norms. Operations Research Letters 32, 6, 510--516.
8. Buchbinder, N., Jain, K., and Naor, J. S. 2007. Online primal-dual algorithms for maximizing ad-auctions revenue. In ESA. Springer, 253--264.
9. Devanur, N. and Hayes, T. 2009. The adwords problem: Online keyword matching with budgeted bidders under random permutations. In EC. 71--78.
10. Devanur, N. R., Jain, K., Sivan, B., and Wilkens, C. A. 2011. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. In EC. ACM, 29--38.
11. Devanur, N. R., Sivan, B., and Azar, Y. 2012. Asymptotically optimal algorithm for stochastic adwords. In Proceedings of the 13th ACM Conference on Electronic Commerce. ACM, 388--404.
12. Feldman, J., Henzinger, M., Korula, N., Mirrokni, V. S., and Stein, C. 2010. Online stochastic packing applied to display ad allocation. In ESA. Springer, 182--194.
13. Feldman, J., Korula, N., Mirrokni, V., Muthukrishnan, S., and Pal, M. 2009a. Online ad assignment with free disposal. In WINE.
14. Feldman, J., Mehta, A., Mirrokni, V., and Muthukrishnan, S. 2009b. Online stochastic matching: Beating 1 - 1/e. In FOCS. 117--126.
15. Haeupler, B., Mirrokni, V., and ZadiMoghaddam, M. 2011. Online stochastic weighted matching: Improved approximation algorithms. In WINE. 170--181.
16. Jaillet, P. and Lu, X. 2013. Online stochastic matching: New algorithms with better bounds. Mathematics of Operations Research 39, 3, 624--646.
17. Kalyanasundaram, B. and Pruhs, K. R. 2000. An optimal deterministic algorithm for online b -matching. Theoretical Computer Science 233, 1--2, 319--325.
18. Karande, C., Mehta, A., and Tripathi, P. 2011. Online bipartite matching with unknown distributions. In STOC. 587--596.
19. Karp, R., Vazirani, U., and Vazirani, V. 1990. An optimal algorithm for online bipartite matching. In STOC. 352--358.
20. Mahdian, M., Nazerzadeh, H., and Saberi, A. 2007. Allocating online advertisement space with unreliable estimates. In Proceedings of the 8th ACM conference on Electronic commerce. ACM, 288--294.
21. Mahdian, M. and Yan, Q. 2011. Online bipartite matching with random arrivals: A strongly factor revealing lp approach. In STOC. 597--606.
22. Mehta, A., Saberi, A., Vazirani, U., and Vazirani, V. 2007. Adwords and generalized online matching. J. ACM 54, 5, 22.
23. Menshadi, V. H., Oveis Gharan, S., and Saberi, A. 2011. Online stochastic matching: Online actions based on offline statistics. In SODA. 1285--1294.
24. Mirrokni, V. S., Oveis Gharan, S., and Zadi Moghaddam, M. 2011. Simultaneous approximations of stochastic and adversarial budgeted allocation problems. In SODA. 1690--1701.
25. Tan, B. and Srikant, R. 2011. Online advertisement, optimization and stochastic networks. In CDC-ECC. IEEE, 4504--4509.
26. Vee, E., Vassilvitskii, S., and Shanmugasundaram, J. 2010. Optimal online assignment with forecasts. In EC. 109--118.
27. Wang, H., Xie, H., Qiu, L., Yang, Y. R., Zhang, Y., and Greenberg, A. 2006. COPE: traffic engineering in dynamic networks. ACM SIGCOMM 36, 4, 99--110.

Index Terms

• Theory of computation

  • Randomness, geometry and discrete structures