Online Matching in Geometric Random Graphs

• 成果类型: Article; Early Access
• 署名作者: Sentenac, Flore; Noiry, Nathan; Lerasle, Matthieu; Menard, Laurent; Perchet, Vianney
• 署名单位: IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Telecom Paris; Institut Polytechnique de Paris; Centre National de la Recherche Scientifique (CNRS); Institut Polytechnique de Paris; ENSAE Paris
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2023.0309
• 发表日期: 2025

摘要

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-an 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 similar enough, meaning that the distance between their respective points is less than c=n, where c > 0 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's 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 worstcase 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.