Batching and Greedy Policies: How Good Are They in Dynamic Matching?

References

• Anderson R, Ashlagi I, Gamarnik D, Kanoria Y (2017) Efficient dynamic barter exchange. Oper. Res. 65(6):1446–1459.Link, Google Scholar
• Aouad A, Saritaç Ö (2022) Dynamic stochastic matching under limited time. Oper. Res. 70(4):2349–2383.Link, Google Scholar
• Ashlagi I, Burq M, Dutta C, Jaillet P, Saberi A, Sholley C (2022) Edge weighted online windowed matching. Math. Oper. Res. 48(2):999–1016.Link, Google Scholar
• Aveklouris A, Puha AL, Ward AR (2024) A fluid approximation for a matching model with general reneging distributions. Queueing Systems 106(3–4):199–238.Crossref, Google Scholar
• Aveklouris A, DeValve L, Stock M, Ward A (2025) Matching impatient and heterogeneous demand and supply. Oper. Res. 73(3):1637–1658. Link, Google Scholar
• Bahmani B, Kapralov M (2010) Improved bounds for online stochastic matching. de Berg M, Meyer U, eds. Algorithms—ESA 2010 (Springer, Berlin), 170–181.Crossref, Google Scholar
• Bailey E, Unnikrishnan A, Lin DY (2011) Models for minimizing backhaul costs through freight collaboration. Transportation Res. Record 2224(1):51–60.Crossref, Google Scholar
• Behnezhad S, Łącki J, Mirrokni V (2020) Fully dynamic matching: Beating 2-approximation in δϵ update time. Chawla S, ed. Proc. 14th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2492–2508.Google Scholar
• Bernstein A, Dudeja A, Langley Z (2021) A framework for dynamic matching in weighted graphs. Khuller S, Williams VV, eds. Proc. 53rd Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 668–681.Google Scholar
• Bhattacharya S, Henzinger M, Nanongkai D (2016) New deterministic approximation algorithms for fully dynamic matching. Mansour Y, Wichs D, eds. Proc. 48th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 398–411.Google Scholar
• Bhattacharya S, Kiss P, Saranurak T, Wajc D (2022) Dynamic matching with better-than-2 approximation in polylogarithmic update time. Preprint, submitted July 15, https://arxiv.org/abs/2207.07438.Google Scholar
• Blanchet J, Reiman M, Shah V, Wein L, Wu L (2022) Asymptotically optimal control of a centralized dynamic matching market with general utilities. Oper. Res. 70(6):3355–3370. Link, Google Scholar
• Brubach B, Sankararaman KA, Srinivasan A, Xu P (2016) New algorithms, better bounds, and a novel model for online stochastic matching. Sankowski P, Zaroliagis C, eds. 24th Annual Eur. Sympos. Algorithms (Schloss Dagstuhl, Wadern, Germany).Google Scholar
• Caballini C, Sacone S, Saeednia M (2013) A decomposition approach for optimizing truck trips for a single carrier. Hegyi A, De Schutter B, eds. 16th Internat. IEEE Conf. Intelligent Transportation Systems (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 1625–1630.Google Scholar
• Caballini C, Sacone S, Saeednia M (2016) Cooperation among truck carriers in seaport containerized transportation. Transportation Res. Part E: Logist. Transportation Rev. 93:38–56.Crossref, Google Scholar
• Castro F, Nazerzadeh H, Yan C (2020) Matching queues with reneging: A product form solution. Queueing Systems 96(3):359–385.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, Cham, Switzerland), 17–30.Google Scholar
• Edmonds J (1965) Maximum matching and a polyhedron with 0, 1-vertices. J. Res. Natl. Bureau Standards B 69(1–2):125–130. Crossref, Google Scholar
• Ezra T, Feldman M, Gravin N, Tang ZG (2022) Prophet matching with general arrivals. Math. Oper. Res. 47(2):878–898.Link, Google Scholar
• Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1/e. Spielman D, ed. IEEE 50th Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC).Google Scholar
• Feng G, Kong G, Wang Z (2021) We are on the way: Analysis of on-demand ride-hailing systems. Manufacturing Service Oper. Management 23(5):1237–1256.Link, Google Scholar
• Gupta V (2024) Greedy algorithm for multiway matching with bounded regret. Oper. Res. 72(3):1139–1155.Link, Google Scholar
• Heilmann K (2020) Information frictions, load matching, and route efficiency in the trucking industry. Preprint, submitted March 24, http://dx.doi.org/10.2139/ssrn.3545019.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
• Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Ortiz H, ed. Proc. 23rd Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 352–358.Google Scholar
• Kerimov S, Ashlagi I, Gurvich I (2024) Dynamic matching: Characterizing and achieving constant regret. Management Sci. 70(5):2799–2822.Link, Google Scholar
• Kerimov S, Ashlagi I, Gurvich I (2025) On the optimality of greedy policies in dynamic matching. Oper. Res. 73(1):560–582. Link, Google Scholar
• Lobel I, Martin S (2025) Detours in shared rides. Management Sci. 71(2):1716–1736.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 (2013) Online matching and ad allocation. Foundations Trends Theoret. Comput. Sci. 8(4):265–368.Crossref, Google Scholar
• Montecinos J, Ouhimmou M, Chauhan S, Paquet M, Gharbi A (2021) Transport carriers’ cooperation on the last-mile delivery in urban areas. Transportation 48(5):2401–2431.Crossref, Google Scholar
• Nazari M, Stolyar AL (2019) Reward maximization in general dynamic matching systems. Queueing Systems 91(1):143–170.Crossref, Google Scholar
• Neiman O, Solomon S (2016) Simple deterministic algorithms for fully dynamic maximal matching. ACM Trans. Algorithms 12(1):7. Crossref, Google Scholar
• NYC Taxi and Limousine Commission (2023) Taxi zone map—Manhattan. Accessed June 21, https://www.nyc.gov/assets/tlc/images/content/pages/about/taxi_zone_map_manhattan.jpg.Google Scholar
• Özkan E, Ward AR (2020) Dynamic matching for real-time ride sharing. Stochastic Systems 10(1):29–70.Link, Google Scholar
• Santi P, Resta G, Szell M, Sobolevsky S, Strogatz SH, Ratti C (2014) Quantifying the benefits of vehicle pooling with shareability networks. Proc. Natl. Acad. Sci. USA 111(37):13290–13294.Crossref, Google Scholar
• Torrico A, Toriello A (2022) Dynamic relaxations for online bipartite matching. INFORMS J. Comput. 34(4):1871–1884.Link, Google Scholar
• Torrico A, Ahmed S, Toriello A (2018) A polyhedral approach to online bipartite matching. Math. Programming 172(1):443–465.Crossref, Google Scholar
• Wang X, Agatz N, Erera A (2018) Stable matching for dynamic ride-sharing systems. Transportation Sci. 52(4):850–867.Link, Google Scholar
• Yan C, Yan J, Shen Y (2025) Pricing shared rides. Oper. Res. Forthcoming.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