5 citations · 17 across the 10 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
cs.DS2020
Adwords in a Panorama
Zhiyi Huang, Qiankun Zhang, Yuhao Zhang
Three decades ago, Karp, Vazirani, and Vazirani (STOC 1990) defined the online matching problem and gave an optimal -competitive algorithm. Fifteen yea…
cs.DS2020★ 5 cited
Fully Online Matching II: Beating Ranking and Water-filling
Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu +1
Karp, Vazirani, and Vazirani (STOC 1990) initiated the study of online bipartite matching, which has held a central role in online algorithms ever since. Of particular importance a…
cs.DS2020★ 3 cited
A Simple 1-1/e Approximation for Oblivious Bipartite Matching
Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang
We study the oblivious matching problem, which aims at finding a maximum matching on a graph with unknown edge set. Any algorithm for the problem specifies an ordering of the verte…