Fully Online Matching with General Stochastic Arrivals and Departures

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
• Aouad A, Saritaç Ö (2020) Dynamic stochastic matching under limited time. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 789–790.Google Scholar
• Ashlagi I, Roth AE (2021) Kidney exchange: An operations perspective. Management Sci. 67(9):5455–5478.Link, Google Scholar
• Ashlagi I, Burq M, Dutta C, Jaillet P, Saberi A, Sholley C (2019) Edge weighted online windowed matching. Proc. 2019 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 729–742.Crossref, Google Scholar
• Ashlagi I, Azar Y, Charikar M, Chiplunkar A, Geri O, Kaplan H, Makhijani R, Wang Y, Wattenhofer R (2017) Min-cost bipartite perfect matching with delays. Jansen K, Rolim JDP, Williamson D, Vempala SS, eds. Approximation Randomization Combin. Optim. Algorithms Techniques (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 1:1–1:20.Google Scholar
• Azar Y, Jacob Fanani A (2020) Deterministic min-cost matching with delays. Theory Comput. Syst. 64(4):572–592. Crossref, Google Scholar
• Azar Y, Chiplunkar A, Kaplan H (2017) Polylogarithmic bounds on the competitiveness of min-cost perfect matching with delays. Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1051–1061.Google Scholar
• Brubach B, Grammel N, Ma W, Srinivasan A (2023) Online matching frameworks under stochastic rewards, product ranking, and unknown patience. Oper. Res. 73(2):995–1010.Google Scholar
• Brubach B, Sankararaman KA, Srinivasan A, Xu P (2020) Attenuate locally, win globally: Attenuation-based frameworks for online stochastic matching with timeouts. Algorithmica 82:64–87.Crossref, Google Scholar
• Chen XA, Wang Z (2015) A dynamic learning algorithm for online matching problems with concave returns. Eur. J. Oper. Res. 247(2):379–388.Crossref, Google Scholar
• Collina N, Immorlica N, Leyton-Brown K, Lucier B, Newman N (2020) Dynamic weighted matching with heterogeneous arrival and departure rates. Chen X, Gravin N, Hoefer M, Mehta R, eds. Internat. Conf. Web Internet Econom. (Springer, Berlin, Heidelberg), 17–30.Google Scholar
• Corem Y, Brown N, Petralia J (2013) Got skillz? Player matching, mastery, and engagement in skill-based games. Proc. First Internat. Conf. Gameful Design Res. Appl. (ACM, New York), 115–118.Google Scholar
• de Ruijter A, Cats O, van Lint H (2024) Ridesourcing platforms thrive on socio-economic inequality. Sci. Rep. 14(1):7371.Crossref, Google Scholar
• Donovan B, Work D (2014) New York City taxi trip data (2010-2013). Technical report, University of Illinois Urbana-Champaign, Champaign.Google Scholar
• Eckl A, Kirschbaum A, Leichter M, Schewior K (2021) A stronger impossibility for fully online matching. Oper. Res. Lett. 49(5):802–808.Crossref, Google Scholar
• Emek Y, Kutten S, Wattenhofer R (2016) Online matching: Haste makes waste! Proc. 48th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 333–344.Google Scholar
• Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1/e. 50th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Atlanta), 117–126.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 (2022) Online matching with stochastic rewards: Optimal competitive ratio via path-based formulation. Oper. Res. 71(2):563–580.Google Scholar
• Hu M, Zhou Y (2022) Dynamic type matching. Manufacturing Service Oper. Management 24(1):125–142.Link, Google Scholar
• Huang Z, Shu X (2021) Online stochastic matching, Poisson arrivals, and the natural linear program. Proc. 53rd Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 682–693.Google Scholar
• Huang Z, Shu X, Yan S (2022) The power of multiple choices in online stochastic matching. Preprint, submitted March 6, https://arxiv.org/abs/2203.02883.Google Scholar
• Huang Z, Tang ZG, Wu X, Zhang Y (2020a) Fully online matching II: Beating ranking and water-filling. IEEE 61st Annual Sympos. Foundations Comput. Sci. (IEEE, Durham, NC), 1380–1391.Google Scholar
• Huang Z, Kang N, Tang ZG, Wu X, Zhang Y, Zhu X (2020b) Fully online matching. J. ACM 67(3):1–25.Crossref, Google Scholar
• Huang Z, Peng B, Tang ZG, Tao R, Wu X, Zhang Y (2019) Tight competitive ratios of classic matching algorithms in the fully online model. Proc. 2019 Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2875–2886.Google Scholar
• Jaillet P, Lu X (2014) Online stochastic matching: New algorithms with better bounds. Math. Oper. Res. 39(3):624–646.Link, Google Scholar
• Kanoria Y (2021) Dynamic spatial matching. Preprint, submitted May 16, https://arxiv.org/abs/2105.07329.Google Scholar
• Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proc. 22nd Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 352–358.Google Scholar
• Kessel K, Shameli A, Saberi A, Wajc D (2022) The stationary prophet inequality problem. Proc. 23rd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 243–244.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
• 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
• Mehta A, Panigrahi D (2012) Online matching with stochastic rewards. IEEE 53rd Annual Sympos. Foundations Comput. Sci. (IEEE, New Brunswick, NJ), 728–737.Google Scholar
• Mehta A, Waggoner B, Zadimoghaddam M (2014) Online stochastic matching with unequal probabilities. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1388–1404.Google Scholar
• Purohit M, Gollapudi S, Raghavan M (2019) Hiring under uncertainty. Kamalika C, Ruslan S, eds. Internat. Conf. Machine Learn., vol. 97 (PMLR, New York), 5181–5189.Google Scholar
• Seneca ESG (2023) China requires ride-hailing platforms to reduce commissions and offer transparency. Accessed October 10, 2024, https://senecaesg.com/insights/china-requires-ride-hailing-platforms-to-reduce-commissions-and-offer-transparency/.Google Scholar
• Wang H, Bei X (2022) Real-time driver-request assignment in ridesourcing. Proc. AAAI Conf. Artificial Intelligence, vol. 36 (Association for the Advancement of Artificial Intelligence, Washington, DC), 3840–3849.Google Scholar
• Xu P (2024) Tight competitive and variance analyses of matching policies in gig platforms. Proc. ACM Web Conf. 2024 (Association for Computing Machinery, New York), 5–13.Google Scholar
• Xu P, Shi Y, Cheng H, Dickerson J, Sankararaman KA, Srinivasan A, Tong Y, Tsepenekas L (2019) A unified approach to online matching with conflict-aware constraints. Proc. AAAI Conf. Artificial Intelligence, vol. 33 (Association for the Advancement of Artificial Intelligence, Washington, DC), 2221–2228.Google Scholar
• Yan C, Zhu H, Korolko N, Woodard D (2020) Dynamic pricing and matching in ride-hailing platforms. Naval Res. Logist. 67(8):705–724.Crossref, Google Scholar