Help
Cart
Skip main navigation

Available Issues

April 10, 2013 - June 5, 2026

Available Issues

April 10, 2013 - June 5, 2026

Adwords with Unknown Budgets and Beyond

Published Online:26 Apr 2024https://doi.org/10.1287/mnsc.2021.03243

References

  • Aggarwal G, Badanidiyuru A, Mehta A (2019) Autobidding with constraints. Caragiannis I, Mirrokni VS, Nikolova E, eds. Proc. Internat. Conf. Web Internet Econom., Lecture Notes in Computer Science, vol. 11920 (Springer, Berlin), 17–30.Google Scholar
  • Aggarwal G, Goel G, Karande C, Mehta A (2011) Online vertex-weighted bipartite matching and single-bid budgeted allocations. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1253–1264.Google Scholar
  • Alaei S, Hajiaghayi M, Liaghat V (2012) Online prophet-inequality matching with applications to ad allocation. Faltings B, Leyton-Brown K, Ipeirotis P, eds. Proc. 13th ACM Conf. Electronic Commerce (ACM, New York), 18–35.Google Scholar
  • Albers S, Schubert S (2021) Optimal algorithms for online b-matching with variable vertex capacities. Wootters M, Sanità L, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Leibniz International Proceedings in Informatics, vol. 207 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 2:1–2:18.Google Scholar
  • Balseiro S, Lu H, Mirrokni V (2023) Dual mirror descent for online allocation problems. Oper. Res. 71(1):101–119.Google Scholar
  • Birnbaum B, Mathieu C (2008) On-line bipartite matching made simple. ACM SIGACT News 39(1):80–87.Crossref, Google Scholar
  • Buchbinder N, Jain K, Naor JS (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. Proc. Eur. Sympos. Algorithms (Springer, Berlin), 253–264.Google Scholar
  • Delong S, Farhadi A, Niazadeh R, Sivan B, Udwani R (2023) Online bipartite matching with reusable resources. Math. Oper. Res., ePub ahead of print October 13, https://doi.org/10.1287/moor.2022.0242.Link, Google Scholar
  • Devanur NR, Hayes TP (2009) The adwords problem: Online keyword matching with budgeted bidders under random permutations. Proc. 10th ACM Conf. Electronic Commerce (ACM, New York), 71–78.Google Scholar
  • Devanur NR, Jain K, Kleinberg RD (2013) Randomized primal-dual analysis of ranking for online bipartite matching. Proc. 24th Annual ACM-SIAM sympos. Discrete Algorithms (SIAM, Philadelphia), 101–107.Google Scholar
  • Devanur NR, Jain K, Sivan B, Wilkens CA (2019) Near optimal online algorithms and fast approximation algorithms for resource allocation problems. J. ACM 66(1):1–41.Crossref, Google Scholar
  • Eden A, Feldman M, Fiat A, Segal K (2021) An economics-based analysis of ranking for online bipartite matching. Proc. Sympos. Simplicity Algorithms (SIAM, Philadelphia), 107–110.Google Scholar
  • Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1/e. Proc. 50th Annual IEEE Sympos. Foundations Computer Sci. (IEEE, New York), 117–126.Google Scholar
  • Goel G, Mehta A (2008) Online budgeted matching in random input models with applications to adwords. Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 982–991.Google Scholar
  • Golrezaei N, Nazerzadeh H, Rusmevichientong P (2014) Real-time optimization of personalized assortments. Management Sci. 60(6):1532–1551.Link, Google Scholar
  • Goyal V, Udwani R (2023) Online matching with stochastic rewards: Optimal competitive ratio via path-based formulation. Oper. Res. 71(2):563–580.Link, Google Scholar
  • Goyal V, Iyengar G, Udwani R (2021) Asymptotically optimal competitive ratio for online allocation of reusable resources. Feldman M, Fu H, Talgam-Cohen I, eds. Proc. Web Internet Economics 17th Internat. Conf., Lecture Notes in Computer Science, vol. 13112 (Springer, Berlin), 543.Google Scholar
  • Huang Z, Zhang Q (2020) Online primal dual meets online matching with stochastic rewards: Configuration lp to the rescue. Proc. 52nd Annual ACM SIGACT Sympos. Theory Comput., 1153–1164.Google Scholar
  • Huang Z, Zhang Q, Zhang Y (2020) Adwords in a panorama. Proc. IEEE 61st Annual Sympos. Foundations Computer Sci. (IEEE, New York), 1416–1426.Google Scholar
  • Kalyanasundaram B, Pruhs KR (2000) An optimal deterministic algorithm for online b-matching. Theoretical Comput. Sci. 233(1–2):319–325.Crossref, Google Scholar
  • Kapralov M, Post I, Vondrák J (2013) Online submodular welfare maximization: Greedy is optimal. Proc. 24th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1216–1225.Google Scholar
  • Karande C, Mehta A, Tripathi P (2011) Online bipartite matching with unknown distributions. Proc. 43rd Annual ACM Sympos. Theory Comput. (ACM, New York), 587–596.Google Scholar
  • Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proc. 22nd Annual ACM Sympos. Theory Comput. (ACM, New York), 352–358.Google Scholar
  • Liang J, Tang ZG, Xu YE, Zhang Y, Zhou R (2023) On the perturbation function of ranking and balance for weighted online bipartite matching. Gørtz IL, Farach-Colton M, Puglisi SJ, Herman G, eds. 31st Annual European Sympos. Algorithms, vol. 274 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 80:1–80:15.Google Scholar
  • Manshadi VH, Gharan SO, Saberi A (2012) Online stochastic matching: Online actions based on offline statistics. Math. Oper. Res. 37(4):559–573.Link, Google Scholar
  • Manshadi V, Rodilitz S, Saban D, Suresh A (2022) Online algorithms for matching platforms with multi-channel traffic. Proc. 23rd ACM Conf. Econom. Comput. (ACM, New York), 986–987.Google Scholar
  • Mehta A (2013) Online matching and ad allocation. Foundations Trends Theoretical Comput. Sci. 8(4):265–368.Crossref, Google Scholar
  • Mehta A, Panigrahi D (2012) Online matching with stochastic rewards. Proc. IEEE 53rd Annual Sympos. Foundations Comput. Sci. (IEEE, New York), 728–737.Google Scholar
  • Mehta A, Waggoner B, Zadimoghaddam M (2015) Online stochastic matching with unequal probabilities. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1388–1404.Google Scholar
  • Mehta A, Saberi A, Vazirani U, Vazirani V (2007) Adwords and generalized online matching. J. ACM 54(5):22-es.Crossref, Google Scholar
  • Mirrokni VS, Gharan SO, Zadimoghaddam M (2012) Simultaneous approximations for adversarial and stochastic online budgeted allocation. Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1690–1701.Google Scholar
  • Udwani R (2024) When stochastic rewards reduce to deterministic rewards in online bipartite matching. Proc. Sympos. Simplicity Algorithms (SIAM, Philadelphia), 321–330.Google Scholar
  • Vazirani VV (2021) Randomized online algorithms for adwords. Preprint, submitted July 22, https://arxiv.org/abs/2107.10777.Google Scholar
  • Vazirani VV (2023) Toward a practical, budget-oblivious algorithm for the adwords problem under small bids. Bouyer P, Srinivasan S, eds. Proc. 43rd IARCS Annual Conf. Foundations Software Technology Theoretical Comput. Sci., vol. 284 of LIPIcs (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Wadern, Germany), 21:1–21:14.Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree