Online Matching with KIID Edge Arrivals (opens in new tab)

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 edg...