Online Matching with Stochastic Rewards: Optimal Competitive Ratio via Path-Based Formulation

References

• Acimovic J, Farias VF (2019) The fulfillment-optimization problem. Operations Research & Management Science in the Age of Analytics (INFORMS), 218–237.Link, 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. on Discrete Algorithms (SIAM, Philadelphia), 1253–1264.Google Scholar
• Aouad A, Saritaç Ö (2022) Dynamic stochastic matching under limited time. Oper. Res. 70(4):2349–2383.Google Scholar
• Ashlagi I, Burq M, Dutta C, Jaillet P, Saberi A, Sholley C (2019) Edge weighted online windowed matching. Karlin A, Immorlica N, Johari R, eds. Proc. 2019 ACM Conf. on Econom. and Comput. (ACM, New York), 729–742.Google Scholar
• Bansal N, Gupta A, Li J, Mestre J, Nagarajan V, Rudra A (2010) When lp is the cure for your matching woes: Improved bounds for stochastic matchings. Proc. Eur. Sympos. on Algorithms (Springer, Berlin), 218–229.Google Scholar
• Birnbaum B, Mathieu C (2008) On-line bipartite matching made simple. ACM SIGACT News 39(1):80–87.Crossref, Google Scholar
• Borodin A, MacRury C, Rakheja A (2020) Bipartite stochastic matching: Online, random order, and i.i.d. models. Preprint, submitted April 29, 2020, https://arxiv.org/abs/2004.14304.Google Scholar
• Buchbinder N, Jain K, Naor JS (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. Proc. Eur. Sympos. on Algorithms (Springer, Berlin), 253–264.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
• Charikar M, Henzinger M, Nguyen HL (2014) Online bipartite matching with decomposable weights. Proc. Eur. Sympos. on Algorithms (Springer, Berlin), 260–271.Google Scholar
• Devanur NR, Hayes TP (2009) The adwords problem: online keyword matching with budgeted bidders under random permutations. Proc. 10th ACM Conf. on 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. on Discrete Algorithms (SIAM, Philadelphia), 101–107.Google Scholar
• Feng Y, Niazadeh R, Saberi A (2019) Linear programming based online policies for real-time assortment of reusable resources. Preprint, submitted July 17, 2019, https://dx.doi.org/10.2139/ssrn.3421227.Google Scholar
• Feng Y, Niazadeh R, Saberi A (2021) Two-stage stochastic matching with application to ride hailing. Marx D, ed. Proc. ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 2862–2877.Google Scholar
• Goel G, Mehta A (2008) Online budgeted matching in random input models with applications to adwords. Proc. 19th Annual ACM-SIAM Sympos. on 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
• Gong X-Y, Goyal V, Iyengar G, Simchi-Levi D, Udwani R, Wang S(2022) Online assortment optimization with reusable resources. Management Sci. 68(7):4772–4785.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 and Internet Econom.: 17th Internat. Conf. vol. 13112 of Lecture Notes in Computer Science (Springer, Berlin), 543.Google Scholar
• Grammel N, Brubach B, Ma W, Srinivasan A (2021) Follow your star: New frameworks for online stochastic matching with known and unknown patience Arindam B, Kenji F, eds. Proc. 24th Internat. Conf. Artificial Intelligence Statis. Proc. Machine Learn. Res., vol. 130 (PMLR), 2872–2880.Google Scholar
• Ho CJ, Vaughan JW (2012) Online Task Assignment in Crowdsourcing Markets, vol. 12 (AAAI, Palo Alto, CA).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. on Theory of Comput. (ACM, New York), 1153–1164.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
• Karger DR, Oh S, Shah D (2014) Budget-optimal task allocation for reliable crowdsourcing systems. Oper. Res. 62(1):1–24.Link, Google Scholar
• Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proc. 22nd Annual ACM Sympos. on Theory of Comput. (ACM, New York), 352–358.Google Scholar
• Le Cam L (1960) An approximation theorem for the poisson binomial distribution. Pacific J. Math. 10(4):1181–1197.Crossref, Google Scholar
• 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
• Mehta A, Panigrahi D (2012) Online matching with stochastic rewards. Proc. IEEE 53rd Annual Sympos. on Foundations of 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. on 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.Crossref, Google Scholar
• Mehta A (2013) Online matching and ad allocation. Foundations Trends Theoretical Comput. Sci. 8(4):265–368.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. on Discrete Algorithms (SIAM, Philadelphia), 1690–1701.Google Scholar
• Udwani R (2021) Adwords with unknown budgets. Preprint, submitted October 1, 2021, https://arxiv.org/abs/2110.00504.Google Scholar