2 citations · 5 across the 16 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
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-…
cs.DS2023
Improved Competitive Ratios for Online Bipartite Matching on Degree Bounded Graphs
Yilong Feng, Xiaowei Wu, Shengwei Zhou
We consider the online bipartite matching problem on -bounded graphs, where each online vertex has at most neighbors, each offline vertex has at least neighbors, and…
cs.DS2023
Improved Competitive Ratio for Edge-Weighted Online Stochastic Matching
Yilong Feng, Guoliang Qiu, Xiaowei Wu +1
We consider the edge-weighted online stochastic matching problem, in which an edge-weighted bipartite graph G=(I\cup J, E) with offline vertices J and online vertex types I is give…