2 papers
cs.DS2026
Online Matching with KIID Edge Arrivals
Yilong Feng, Haolong Li, Xiaowei Wu
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 arri…
cs.DS2025
Degree-bounded Online Bipartite Matching: OCS vs. Ranking
Yilong Feng, Haolong Li, Xiaowei Wu +1
We revisit the online bipartite matching problem on -regular graphs, for which Cohen and Wajc (SODA 2018) proposed an algorithm with a competitive ratio of $1-2\sqrt{H_d/d} = 1-…