{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T10:37:45Z","timestamp":1774003065120,"version":"3.50.1"},"reference-count":39,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Operations Research"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:p>A Novel Fully Online Matching Algorithm in Stochastic Environments<\/jats:p>\n                  <jats:p>In many modern applications, such as ride-sharing, participants arrive and depart dynamically, requiring quick decisions about who to match and when. In \u201cFully Online Matching with General Stochastic Arrivals and Departures,\u201d Li, Wang, and Yan introduce a fully online matching framework that models these real-world dynamics. Each arrival follows a known identical and independent distribution over agent types, whereas the sojourn time is unknown in advance and follows type-specific distributions with known expectations. To address this, they propose a linear programming\u2013based algorithm that guarantees a competitive ratio of at least 0.192 under mild conditions\u2014more than 50% better than the state-of-the-art result of 0.125. They also establish several hardness results to highlight the intrinsic difficulty of the problem. Numerical experiments further confirm the effectiveness and efficiency of their algorithm, offering new insights for decision making in stochastic and dynamic environments.<\/jats:p>","DOI":"10.1287\/opre.2023.0190","type":"journal-article","created":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T14:34:51Z","timestamp":1762785291000},"page":"752-769","source":"Crossref","is-referenced-by-count":0,"title":["Fully Online Matching with General Stochastic Arrivals and Departures"],"prefix":"10.1287","volume":"74","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5287-2247","authenticated-orcid":false,"given":"Zihao","family":"Li","sequence":"first","affiliation":[{"name":"Institute of Operations Research and Analytics, National University of Singapore, Singapore 119077"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3001-107X","authenticated-orcid":false,"given":"Hao","family":"Wang","sequence":"additional","affiliation":[{"name":"Faculty of Business for Science and Technology, School of Management, University of Science and Technology of China, Anhui 230026, People\u2019s Republic of China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7370-9959","authenticated-orcid":false,"given":"Zhenzhen","family":"Yan","sequence":"additional","affiliation":[{"name":"School of Physical and Mathematical Sciences & Nanyang Business School, Nanyang Technological University, Singapore 639798"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"crossref","unstructured":"Aggarwal G, Goel G, Karande C, Mehta A (2011) Online vertex-weighted bipartite matching and single-bid budgeted allocations.\n                      Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms\n                      (SIAM, Philadelphia), 1253\u20131264.","DOI":"10.1137\/1.9781611973082.95"},{"key":"B2","doi-asserted-by":"crossref","unstructured":"Aouad A, Sarita\u00e7 \u00d6 (2020) Dynamic stochastic matching under limited time.\n                      Proc. 21st ACM Conf. Econom. Comput.\n                      (Association for Computing Machinery, New York), 789\u2013790.","DOI":"10.1145\/3391403.3399524"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2020.3954"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329573"},{"key":"B5","unstructured":"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.\n                      Approximation Randomization Combin. Optim. Algorithms Techniques\n                      (Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany), 1:1\u20131:20."},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-019-09963-7"},{"key":"B7","doi-asserted-by":"crossref","unstructured":"Azar Y, Chiplunkar A, Kaplan H (2017) Polylogarithmic bounds on the competitiveness of min-cost perfect matching with delays.\n                      Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms\n                      (SIAM, Philadelphia), 1051\u20131061.","DOI":"10.1137\/1.9781611974782.67"},{"key":"B8","author":"Brubach B","year":"2023","journal-title":"Oper. Res."},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00603-7"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2015.06.029"},{"key":"B11","doi-asserted-by":"crossref","unstructured":"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.\n                      Internat. Conf. Web Internet Econom\n                      . (Springer, Berlin, Heidelberg), 17\u201330.","DOI":"10.1007\/978-3-030-64946-3_2"},{"key":"B12","doi-asserted-by":"crossref","unstructured":"Corem Y, Brown N, Petralia J (2013) Got skillz? Player matching, mastery, and engagement in skill-based games.\n                      Proc. First Internat. Conf. Gameful Design Res. Appl.\n                      (ACM, New York), 115\u2013118.","DOI":"10.1145\/2583008.2583028"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-024-57540-x"},{"key":"B14","unstructured":"Donovan B, Work D (2014) New York City taxi trip data (2010-2013). Technical report, University of Illinois Urbana-Champaign, Champaign."},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2021.08.012"},{"key":"B16","doi-asserted-by":"crossref","unstructured":"Emek Y, Kutten S, Wattenhofer R (2016) Online matching: Haste makes waste!\n                      Proc. 48th Annual ACM Sympos. Theory Comput.\n                      (Association for Computing Machinery, New York), 333\u2013344.","DOI":"10.1145\/2897518.2897557"},{"key":"B17","doi-asserted-by":"crossref","unstructured":"Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1\/e.\n                      50th Annual IEEE Sympos. Foundations Comput. Sci.\n                      (IEEE, Atlanta), 117\u2013126.","DOI":"10.1109\/FOCS.2009.72"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2014.1939"},{"key":"B19","volume-title":"Oper. Res.","author":"Goyal V","year":"2022"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1287\/msom.2020.0952"},{"key":"B21","doi-asserted-by":"crossref","unstructured":"Huang Z, Shu X (2021) Online stochastic matching, Poisson arrivals, and the natural linear program.\n                      Proc. 53rd Annual ACM SIGACT Sympos. Theory Comput.\n                      (Association for Computing Machinery, New York), 682\u2013693.","DOI":"10.1145\/3406325.3451079"},{"key":"B22","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1145\/3519935.3520046"},{"key":"B23","doi-asserted-by":"crossref","unstructured":"Huang Z, Tang ZG, Wu X, Zhang Y (2020a) Fully online matching II: Beating ranking and water-filling.\n                      IEEE 61st Annual Sympos. Foundations Comput. Sci.\n                      (IEEE, Durham, NC), 1380\u20131391.","DOI":"10.1109\/FOCS46700.2020.00130"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1145\/3390890"},{"key":"B25","doi-asserted-by":"crossref","unstructured":"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.\n                      Proc. 2019 Annual ACM-SIAM Sympos. Discrete Algorithms\n                      (Society for Industrial and Applied Mathematics, Philadelphia), 2875\u20132886.","DOI":"10.1137\/1.9781611975482.178"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0621"},{"key":"B27","unstructured":"Kanoria Y (2021) Dynamic spatial matching. Preprint, submitted May 16, https:\/\/arxiv.org\/abs\/2105.07329."},{"key":"B28","doi-asserted-by":"crossref","unstructured":"Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching.\n                      Proc. 22nd Annual ACM Sympos. Theory Comput\n                      . (Association for Computing Machinery, New York), 352\u2013358.","DOI":"10.1145\/100216.100262"},{"key":"B29","doi-asserted-by":"crossref","unstructured":"Kessel K, Shameli A, Saberi A, Wajc D (2022) The stationary prophet inequality problem.\n                      Proc. 23rd ACM Conf. Econom. Comput.\n                      (Association for Computing Machinery, New York), 243\u2013244.","DOI":"10.1145\/3490486.3538374"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2019.1957"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1120.0551"},{"key":"B32","doi-asserted-by":"crossref","unstructured":"Mehta A, Panigrahi D (2012) Online matching with stochastic rewards.\n                      IEEE 53rd Annual Sympos. Foundations Comput. Sci.\n                      (IEEE, New Brunswick, NJ), 728\u2013737.","DOI":"10.1109\/FOCS.2012.65"},{"key":"B33","doi-asserted-by":"crossref","unstructured":"Mehta A, Waggoner B, Zadimoghaddam M (2014) Online stochastic matching with unequal probabilities.\n                      Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms\n                      (SIAM, Philadelphia), 1388\u20131404.","DOI":"10.1137\/1.9781611973730.92"},{"key":"B34","doi-asserted-by":"crossref","unstructured":"Purohit M, Gollapudi S, Raghavan M (2019) Hiring under uncertainty. Kamalika C, Ruslan S, eds.\n                      Internat. Conf. Machine Learn.\n                      , vol. 97 (PMLR, New York), 5181\u20135189.","DOI":"10.1007\/978-1-4842-4261-2_5"},{"key":"B35","unstructured":"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\/."},{"key":"B36","doi-asserted-by":"crossref","unstructured":"Wang H, Bei X (2022) Real-time driver-request assignment in ridesourcing.\n                      Proc. AAAI Conf. Artificial Intelligence\n                      , vol. 36 (Association for the Advancement of Artificial Intelligence, Washington, DC), 3840\u20133849.","DOI":"10.1609\/aaai.v36i4.20299"},{"key":"B37","doi-asserted-by":"crossref","unstructured":"Xu P (2024) Tight competitive and variance analyses of matching policies in gig platforms.\n                      Proc. ACM Web Conf. 2024\n                      (Association for Computing Machinery, New York), 5\u201313.","DOI":"10.1145\/3589334.3645335"},{"key":"B38","doi-asserted-by":"crossref","unstructured":"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.\n                      Proc. AAAI Conf. Artificial Intelligence\n                      , vol. 33 (Association for the Advancement of Artificial Intelligence, Washington, DC), 2221\u20132228.","DOI":"10.1609\/aaai.v33i01.33012221"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1002\/nav.21872"}],"container-title":["Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/opre.2023.0190","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T08:13:03Z","timestamp":1773994383000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/opre.2023.0190"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["10.1287\/opre.2023.0190"],"URL":"https:\/\/doi.org\/10.1287\/opre.2023.0190","relation":{},"ISSN":["0030-364X","1526-5463"],"issn-type":[{"value":"0030-364X","type":"print"},{"value":"1526-5463","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3]]}}}