Online Matching with KIID Edge Arrivals
2026-06-15 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study a new version of an online matching problem where edges (connections) arrive one by one from a known graph, rather than just one side of the graph. They find that a simple greedy approach can only do so well, but a previously known algorithm called Suggested Matching performs better, matching known results for vertex arrivals. Then, they create a new two-step algorithm that combines these methods and does even better than the previous best. Their work shows it’s possible to get improved results in this harder edge arrival setting using known input distributions.
online stochastic matchingcompetitive ratiobipartite graphedge arrival modelgreedy algorithmsuggested matching algorithmintegral arrival ratesnatural linear program (LP)KIID (independent identical sampling)vertex arrival model
Authors
Yilong Feng, Haolong Li, Xiaowei Wu
Abstract
In the classic online stochastic matching proposed by Feldman et al. (FOCS 2009), there is a known bipartite type-graph, where one side of the graph is given offline. Upon the arrival of each online vertex, its type is sampled independently and identically from the other side of the type-graph. This model has been extensively studied over the past decade, yielding a rich body of theoretical results. In this paper, we initiate the study of an edge arrival model for online stochastic matching. In our model, the online edges are sampled independently and identically (KIID) from a known type-graph, which need not be bipartite. We first show that the Greedy algorithm cannot achieve a competitive ratio strictly better than $0.5$ while the Suggested Matching algorithm has a competitive ratio of $1-1/e$ under the assumption of integral arrival rates, matching its performance in the one-sided vertex arrival model. We then propose a two-stage algorithm that combines Greedy and Suggested Matching, and show that its competitive ratio is strictly higher than $1-1/e$ for integral arrival rates. While our algorithm is simple, its analysis is intricate and builds upon the Natural LP, which has been proven very powerful in vertex arrival models. Our result reveals that even in the more challenging edge arrival setting for general graphs, competitive ratios better than $1-1/e$ are still possible, given the known distributions.