Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources

References

• 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. Proc. 13th ACM Conf. Electronic Commerce (ACM, New York), 18–35.Google Scholar
• Alon N, Awerbuch B, Azar Y (2003) The online set cover problem. Proc. 35th Annual ACM Sympos. Theory Computing, 100–105.Google Scholar
• Andrews JM, Farias VF, Khojandi AI, Yan CM (2019) Primal–dual algorithms for order fulfillment at Urban Outfitters, Inc. Interfaces 49(5):355–370.Google Scholar
• Aouad A, Saban D (2023) Online assortment optimization for two-sided matching platforms. Management Sci. 69(4):2069–2087.Link, Google Scholar
• Azar Y, Broder AZ, Karlin AR (1994) On-line load balancing. Theoret. Comput. Sci. 130(1):73–84.Crossref, Google Scholar
• Azar Y, Kalyanasundaram B, Plotkin S, Pruhs KR, Waarts O (1993) Online load balancing of temporary tasks. Workshop Algorithms Data Structures (Springer, New York), 119–130.Crossref, Google Scholar
• Bansal N, Buchbinder N, Madry A, Naor J (2015) A polylogarithmic-competitive algorithm for the k-server problem. J. ACM 62(5):1–49.Crossref, Google Scholar
• Besbes O, Elmachtoub AN, Sun Y (2020) Pricing analytics for rotable spare parts. INFORMS J. Appl. Anal. 50(5):313–324.Link, Google Scholar
• Birnbaum B, Mathieu C (2008) On-line bipartite matching made simple. Sigact News 39(1):80–87.Crossref, Google Scholar
• Blum A, Burch C, Kalai A (1999) Finely-competitive paging. 40th Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 450–457.Google Scholar
• Buchbinder N, Jain K, Naor JS (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. Eur. Sympos. Algorithms (Springer, Berlin, Heidelberg), 253–264.Crossref, Google Scholar
• Chan CW, Farias VF (2009) Stochastic depletion problems: Effective myopic policies for a class of dynamic optimization problems. Math. Oper. Res. 34(2):333–350.Link, Google Scholar
• Chen X, Ma W, Simchi-Levi D, Xin L (2023) Assortment planning for recommendations at checkout under inventory constraints. Math. Oper. Res. 49(1):297–325.Google Scholar
• Cruise J, Jonckheere M, Shneer S (2020) Stability of JSQ in queues with general server-job class compatibilities. Queueing Systems 95:271–279.Crossref, Google Scholar
• Delong S, Farhadi A, Niazadeh R, Sivan B, Udwani R (2023) Online bipartite matching with reusable resources. Math. Oper. Res. 49(3):1825–1854.Link, 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 (Society for Industrial and Applied Mathematics, Philadelphia), 101–107.Google Scholar
• Devanur NR, Sivan B, Azar Y (2012) Asymptotically optimal algorithm for stochastic Adwords. Proc. 13th ACM Conf. Electronic Commerce (ACM, New York), 388–404.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
• Dickerson JP, Sankararaman KA, Srinivasan A, Xu P (2018) Allocation problems in ride-sharing platforms: Online matching with offline reusable resources. 32nd AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 1007–1014.Google Scholar
• Elmachtoub AN, Goyal V, Lederman R, Sheth H (2022) Revenue management with product retirement and customer selection. Preprint, submitted February 16, https://dx.doi.org/10.2139/ssrn.4033922.Google Scholar
• Feldman J, Korula N, Mirrokni V, Muthukrishnan S, Pál M (2009) Online ad assignment with free disposal. Internat. Workshop Internet Network Econom. (Springer, Berlin, Heidelberg), 374–385.Crossref, Google Scholar
• Feng Y, Niazadeh R, Saberi A (2021) Robustness of online inventory balancing to inventory shocks. Preprint, submitted March 2, https://dx.doi.org/10.2139/ssrn.3795056.Google Scholar
• Feng Y, Niazadeh R, Saberi A (2022) Near-optimal Bayesian online assortment of reusable resources. Pennock DM, Segal I, Seuken S, eds. The 23rd ACM Conf. Econom. Comput. (ACM, New York), 964–965.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 (Society for Industrial and Applied Mathematics, 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
• Gong XY, Goyal V, Iyengar GN, Simchi-Levi D, Udwani R, Wang S (2022) Online assortment optimization with reusable resources. Management Sci. 68(7):4772–4785.Link, Google Scholar
• Goyal V, Udwani R (2022) Online matching with stochastic rewards: Optimal competitive ratio via path-based formulation. Oper. Res. 71(2):563–580.Google Scholar
• Goyal V, Iyengar G, Udwani R (2022) Pricing a finite inventory of substitutable products with show-all constraint. Preprint, submitted March 22, https://dx.doi.org/10.2139/ssrn.4055722.Google Scholar
• Huang Z, Tang ZG, Wajc D (2024a) Online matching: A brief survey. Preprint, submitted July 7, https://arxiv.org/abs/2407.05381.Google Scholar
• Huang Z, Zhang Q, Zhang Y (2024b) Adwords in a panorama. SIAM J. Comput. 53(3):701–763.Crossref, Google Scholar
• Kalyanasundaram B, Pruhs KR (2000) An optimal deterministic algorithm for online b-matching. Theoret. 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
• 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
• 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
• Megow N, Uetz M, Vredeveld T (2006) Models and algorithms for stochastic online scheduling. Math. Oper. Res. 31(3):513–525.Link, Google Scholar
• Mehta A (2013) Online matching and ad allocation. Foundations Theoret. Comput. Sci. 8(4):265–368.Crossref, Google Scholar
• Mehta A, Panigrahi D (2012) Online matching with stochastic rewards. IEEE 53rd Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 728–737.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
• Rusmevichientong P, Sumida M, Topaloglu H (2020) Dynamic assortment optimization for reusable products with random usage durations. Management Sci. 66(7):2820–2844.Link, Google Scholar
• Udwani R (2022) Periodic reranking for online matching of reusable resources. Proc. 23rd ACM Conf. Econom. Comput. (ACM, New York), 966.Google Scholar
• Udwani R (2024a) Adwords with unknown budgets and beyond. Management Sci., ePub ahead of print April 26, https://doi.org/10.1287/mnsc.2021.03243.Link, Google Scholar
• Udwani R (2024b) Online submodular welfare maximization meets post-allocation stochasticity and reusability. Preprint, submitted March 26, https://arxiv.org/abs/2403.18059.Google Scholar
• Weng W, Zhou X, Srikant R (2020) Optimal load balancing with locality constraints. Proc. ACM Measurement Anal. Comput. Systems 4(3):1–37.Crossref, Google Scholar