Online Bipartite Matching with Reusable Resources

References

• [1] 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 (ACM-SIAM, New York), 1253–1264.Google Scholar
• [2] Agrawal S, Devanur NR (2014) Fast algorithms for online stochastic convex programming. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (ACM-SIAM, New York), 1405–1424.Google Scholar
• [3] 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
• [4] Baek J, Ma W (2022) Bifurcating constraints to improve approximation ratios for network revenue management with reusable resources. Oper. Res. 70(4):2226–2236.Google Scholar
• [5] Bahmani B, Kapralov M (2010) Improved bounds for online stochastic matching. Eur.n Sympos. Algorithms (Springer, Berlin), 170–181.Google Scholar
• [6] Birnbaum B, Mathieu C (2008) On-line bipartite matching made simple. ACM SIGACT News 39(1):80–87.Crossref, Google Scholar
• [7] Blanc G, Charikar M (2022) Multiway online correlated selection. 2021 IEEE 62nd Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 1277–1284.Google Scholar
• [8] Buchbinder N, Jain K, Naor JS (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. Eur. Sympos. Algorithms (Springer, Berlin), 253–264.Google Scholar
• [9] Delong S, Farhadi A, Niazadeh R, Sivan B (2022) Online bipartite matching with reusable resources. Proc. 23rd ACM Conf. Econom. Comput. (ACM, New York), 962–963.Google Scholar
• [10] 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
• [11] Devanur NR, Jain K (2012) Online matching with concave returns. Proc. 44th Annual ACM Sympos. Theory Comput. (ACM, New York), 137–144.Google Scholar
• [12] 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
• [13] 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.Google Scholar
• [14] Dickerson JP, Sankararaman KA, Srinivasan A, Xu P (2021) Allocation problems in ride-sharing platforms: Online matching with offline reusable resources. ACM Trans. Econom. Comput. 9(3):1–17.Google Scholar
• [15] Eden A, Feldman M, Fiat A, Segal K (2021) An economics-based analysis of ranking for online bipartite matching. Sympos. Simplicity Algorithms (SIAM, Philadelphia), 107–110.Google Scholar
• [16] Esfandiari H, Korula N, Mirrokni V (2018) Allocation with traffic spikes: Mixing adversarial and stochastic models. ACM Trans. Econom. Comput. 6(3–4):1–23.Google Scholar
• [17] Fahrbach M, Huang Z, Tao R, Zadimoghaddam M (2020) Edge-weighted online bipartite matching. 2020 IEEE 61st Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 412–423.Google Scholar
• [18] Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1/e. 50th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 117–126.Google Scholar
• [19] Feldman J, Henzinger M, Korula N, Mirrokni VS, Stein C (2010) Online stochastic packing applied to display ad allocation. Eur. Sympo. Algorithms (Springer, Berlin), 182–194.Google Scholar
• [20] 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), 374–385.Google Scholar
• [21] Feng Y, Niazadeh R (2020) Batching and optimal multi-stage bipartite allocations. Chicago Booth Research Paper 20-29, IL.Google Scholar
• [22] Feng Y, Niazadeh R, Saberi A (2019) Linear programming based online policies for real-time assortment of reusable resources. Preprint, submitted July 17, https://dx.doi.org/10.2139/ssrn.3421227.Google Scholar
• [23] Feng Y, Niazadeh R, Saberi A (2020) Near-optimal Bayesian online assortment of reusable resources. Preprint, submitted October 21, https://dx.doi.org/10.2139/ssrn.3714338.Google Scholar
• [24] Feng Y, Niazadeh R, Saberi A (2021a) Online assortment of reusable resources with exogenous replenishment. Preprint, submitted March 2, https://dx.doi.org/10.2139/ssrn.3795056.Google Scholar
• [25] Feng Y, Niazadeh R, Saberi A (2021b) Two-stage stochastic matching with application to ride hailing. Proc. 2021 ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2862–2877.Google Scholar
• [26] Gao R, He Z, Huang Z, Nie Z, Yuan B, Zhong Y (2022) Improved online correlated selection. 2021 IEEE 62nd Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 1265–1276.Google Scholar
• [27] 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
• [28] Golrezaei N, Nazerzadeh H, Rusmevichientong P (2014) Real-time optimization of personalized assortments. Management Sci. 60(6):1532–1551.Link, Google Scholar
• [29] Gong XY, Goyal V, Iyengar GN, Simchi-Levi D, Udwani R, Wang S (2021) Online assortment optimization with reusable resources. Management Sci. 68(7):4772–4785.Link, Google Scholar
• [30] Goyal V, Udwani R (2023) Online matching with stochastic rewards: Optimal competitive ratio via path based formulation. Oper. Res. 71(2):563–580.Google Scholar
• [31] Goyal V, Iyengar G, Udwani R (2020) Online allocation of reusable resources: Achieving optimal competitive ratio. Preprint, submitted February 6, https://arxiv.org/abs/2002.02430.Google Scholar
• [32] 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. Web Internet Econom. 17th Internat. Conf. Proc., Lecture Notes in Computer Science, vol. 13112 (Springer, Berlin), 543.Google Scholar
• [33] Huang Z, Zhang Q (2020) Online primal dual meets online matching with stochastic rewards: Configuration LP to the rescue. Proc. 52nd Annual ACM SIGACT Sympo. Theory Comput. (ACM, New York), 1153–1164.Google Scholar
• [34] Huang Z, Zhang Q, Zhang Y (2020) Adwords in a panorama. 2020 IEEE 61st Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 1416–1426.Google Scholar
• [35] Huang Z, Tang ZG, Wu X, Zhang Y (2020) Fully online matching II: Beating ranking and water-filling. Preprint, submitted May 13, https://arxiv.org/abs/2005.06311.Google Scholar
• [36] Jaillet P, Lu X (2013) Online stochastic matching: New algorithms with better bounds. Math. Oper. Res. 39(3):624–646.Link, Google Scholar
• [37] Kalyanasundaram B, Pruhs KR (2000) An optimal deterministic algorithm for online b-matching. Theoretical Comput. Sci. 233(1–2):319–325.Crossref, Google Scholar
• [38] 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
• [39] Ma W, Simchi-Levi D (2020) Algorithms for online matching, assortment, and pricing with tight weight-dependent competitive ratios. Oper. Res. 68(6):1787–1803.Link, Google Scholar
• [40] Ma W, Simchi-Levi D, Zhao J (2021) Dynamic pricing (and assortment) under a static calendar. Management Sci. 67(4):2292–2313.Link, Google Scholar
• [41] 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
• [42] Mehta A (2013) Online matching and ad allocation. Foundations Trends Theoretical Comput. Sci. 8(4):265–368.Crossref, Google Scholar
• [43] Mehta A, Panigrahi D (2012) Online matching with stochastic rewards. 2012 IEEE 53rd Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 728–737.Google Scholar
• [44] Mehta A, Waggoner B, Zadimoghaddam M (2015) Online stochastic matching with unequal probabilities. Proc. 26th Annual ACM-SIAM Symposium Discrete Algorithms (SIAM, Philadelphia), 1388–1404.Google Scholar
• [45] Mehta A, Saberi A, Vazirani U, Vazirani V (2007) Adwords and generalized online matching. J. ACM 54(5):22-es.Crossref, Google Scholar
• [46] Moharir S, Sanghavi S, Shakkottai S (2015) Online load balancing under graph constraints. IEEE/ACM Trans. Networking 24(3):1690–1703.Crossref, Google Scholar
• [47] 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
• [48] Udwani R (2022) Periodic reranking for online matching of reusable resources. Proc. 23rd ACM Conf. Econom. Comput. (ACM, New York), 966–966.Google Scholar