{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T09:10:41Z","timestamp":1778231441183,"version":"3.51.4"},"reference-count":25,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematics of OR"],"published-print":{"date-parts":[[2026,5]]},"abstract":"<jats:p>We investigate online maximum cardinality matching, a central problem in ad allocation. In this problem, users are revealed sequentially, and each new user can be paired with any previously unmatched campaign that it is compatible with. Despite the limited theoretical guarantees, the greedy algorithm, which matches incoming users with any available campaign, exhibits outstanding performance in practice. Some theoretical support for this practical success has been established in specific classes of graphs, where the connections between different vertices lack strong correlations\u2014an assumption not always valid in real-world situations. To bridge this gap, we focus on the following model; both users and campaigns are represented as points uniformly distributed in the interval [0, 1], and a user is eligible to be paired with a campaign if they are \u201csimilar enough,\u201d meaning that the distance between their respective points is less than [Formula: see text], where [Formula: see text] is a model parameter. As a benchmark, we determine the size of the optimal offline matching in these bipartite one-dimensional random geometric graphs. We achieve this by introducing an algorithm that constructs a maximum matching and analyzing it. We then turn to the online setting and investigate the number of matches made by the online algorithm Closest, which pairs incoming points with their nearest available neighbors in a greedy manner. We demonstrate that the algorithm\u2019s performance can be compared with its fluid limit, which is completely characterized as the solution of a specific partial differential equation (PDE). From this PDE solution, we can compute the competitive ratio of Closest, and our computations reveal that it remains significantly better than its worst-case guarantee. This model turns out to be closely related to the online minimum cost matching problem, and we can extend the results obtained here to refine certain findings in that area of research. Specifically, we determine the exact asymptotic cost of Closest in the small excess regime, providing a more accurate estimate than the previously known loose upper bound.<\/jats:p>\n                  <jats:p>Funding: M. Lerasle\u2019s research is supported by Agency (ANR), \u201cInvestissements d\u2019Avenir\u201d [LabEx Ecodec\/ANR-11-LABX-0047]. This research was supported in part by the French National Research Agency (ANR) in the framework of the PEPR IA FOUNDRY project [ANR-23-PEIA-0003] and through the Grant DOOM ANR23-CE23-0002. It was also funded by the European Union [ERC, Ocean, 101071601]. L. M\u00e9nard\u2019s research is supported by the ANR grant ProGraM [ANR-19-CE40-0025].<\/jats:p>","DOI":"10.1287\/moor.2023.0309","type":"journal-article","created":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T12:24:14Z","timestamp":1749644654000},"page":"1585-1625","source":"Crossref","is-referenced-by-count":1,"title":["Online Matching in Geometric Random Graphs"],"prefix":"10.1287","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-3847-5794","authenticated-orcid":false,"given":"Flore","family":"Sentenac","sequence":"first","affiliation":[{"name":"\u00c9cole des hautes \u00e9tudes commerciales de Paris, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nathan","family":"Noiry","sequence":"additional","affiliation":[{"name":"Statistique Signal et Apprentissage, Telecom Paris, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthieu","family":"Lerasle","sequence":"additional","affiliation":[{"name":"Center for Research in Economics and Statistics, \u00c9cole nationale de la statistique et de l\u2019administration \u00e9conomique IP (Institut Polytechnique) Paris, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laurent","family":"M\u00e9nard","sequence":"additional","affiliation":[{"name":"Modal\u2019X, Unit\u00e9 mixte de recherche Centre national de la recherche scientifique 9023, UPL, University of Paris Nanterre, Nanterre, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vianney","family":"Perchet","sequence":"additional","affiliation":[{"name":"CREST, ENSAE, CRITEO Artificial Intelligence Lab, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.52202\/068431-0414"},{"key":"B2","doi-asserted-by":"crossref","unstructured":"Akbarpour M, Alimohammadi Y, Li S, Saberi A (2021) The value of excess supply in spatial matching markets. Preprint, submitted April 7, http:\/\/dx.doi.org\/10.48550\/ARXIV.2104.03219.","DOI":"10.1145\/3490486.3538375"},{"key":"B3","doi-asserted-by":"crossref","unstructured":"Balkanski E, Faenza Y, Perivier N (2023) The power of greedy for online minimum cost matching on the line.\n                      Proc. 24th ACM Conf. Econom. Comput.\n                      (ACM, New York).","DOI":"10.1145\/3580507.3597794"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1145\/1360443.1360462"},{"key":"B5","unstructured":"Blaszczyszyn B (2017) Lecture notes on random geometric models\u2014Random graphs, point processes and stochastic geometry. https:\/\/hal.inria.fr\/cel-01654766."},{"key":"B6","doi-asserted-by":"crossref","unstructured":"Borodin A, Karavasilis C, Pankratov D (2020) An experimental study of algorithms for online bipartite matching.\n                      J. Experiment. Algorithmics\n                      25:1\u201337.","DOI":"10.1145\/3379552"},{"key":"B7","doi-asserted-by":"crossref","unstructured":"Brubach B, Sankararaman KA, Srinivasan A, Xu P (2020) Online stochastic matching: New algorithms and bounds.\n                      Algorithmica\n                      82(10):2737\u20132783.","DOI":"10.1007\/s00453-020-00698-3"},{"key":"B8","doi-asserted-by":"crossref","unstructured":"Devanur N, Jain K, Kleinberg R (2013) Randomized primal-dual analysis of ranking for online bipartite matching.\n                      Proc. SODA \u201813.","DOI":"10.1137\/1.9781611973105.7"},{"key":"B9","doi-asserted-by":"crossref","unstructured":"Enriquez N, Faraud G, M\u00e9nard L, Noiry N (2022) Depth first exploration of a configuration model.\n                      Electronic J. Probab.\n                      27:1\u201327.","DOI":"10.1214\/22-EJP762"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1137\/0219045"},{"key":"B11","unstructured":"Goel G, Mehta A (2008) Online budgeted matching in random input models with applications to adwords.\n                      Proc. Annual ACM-SIAM Sympos. Discrete Algorithms\n                      (ACM, New York), 982\u2013991."},{"key":"B12","unstructured":"Gupta A, Guruganesh G, Peng B, Wajc D (2019) Stochastic online metric matching. Preprint, submitted April 19, https:\/\/arxiv.org\/abs\/1904.09284."},{"key":"B13","unstructured":"Hayes TP (2005) A large-deviation inequality for vector-valued martingales.\n                      Combinatorics, Probab. Comput.\n                      37."},{"key":"B14","doi-asserted-by":"crossref","unstructured":"Huang Z, Shu X, Yan S (2022) The power of multiple choices in online stochastic matching.\n                      Proc. 54th Annual ACM SIGACT Sympos. Theory Comput.\n                      (Association for Computing Machinery, New York).","DOI":"10.1145\/3519935.3520046"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0621"},{"key":"B16","doi-asserted-by":"crossref","unstructured":"Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching.\n                      Proc. Twenty-Second Annual ACM Sympos. Theory Comput.\n                      (Association for Computing Machinery, New York), 352\u2013358.","DOI":"10.1145\/100216.100262"},{"key":"B17","doi-asserted-by":"crossref","unstructured":"Mahdian M, Yan Q (2011) Online bipartite matching with random arrivals: An approach based on strongly factor-revealing LPs.\n                      Proc. Annual ACM Sympos. Theory Comput.\n                      (Association for Computing Machinery, New York), 597\u2013606.","DOI":"10.1145\/1993636.1993716"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1120.0551"},{"key":"B19","unstructured":"Mastin A, Jaillet P (2013) Greedy online bipartite matching on random graphs. Preprint, submitted July 9, https:\/\/arxiv.org\/abs\/1307.2536."},{"issue":"4","key":"B20","first-page":"265","volume":"8","author":"Mehta A","year":"2012","journal-title":"Theoret. Comput. Sci."},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2014.01.013"},{"key":"B22","unstructured":"Noiry N, Sentenac F, Perchet V (2021) Online matching in sparse random graphs: Non-asymptotic performances of greedy algorithm.\n                      NeurIPS\n                      ."},{"key":"B23","unstructured":"Warnke L (2019) On Wormald\u2019s differential equation method. Preprint, submitted May 22, https:\/\/arxiv.org\/abs\/1905.08928."},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177004612"},{"key":"B25","first-page":"73","volume-title":"Lectures on Approximation and Randomized Algorithms","author":"Wormald NC","year":"1999"}],"container-title":["Mathematics of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/moor.2023.0309","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T08:26:49Z","timestamp":1778228809000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/moor.2023.0309"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["10.1287\/moor.2023.0309"],"URL":"https:\/\/doi.org\/10.1287\/moor.2023.0309","relation":{},"ISSN":["0364-765X","1526-5471"],"issn-type":[{"value":"0364-765X","type":"print"},{"value":"1526-5471","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5]]}}}