12 citations · 44 across the 13 of their papers we have counts for
9 papers · 1 filter
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…
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…
Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai +1
In the dynamic minimum set cover problem, a challenge is to minimize the update time while guaranteeing close to the optimal approximation factor. (Throughout,…
Well-behaved Online Load Balancing Against Strategic Jobs
Bo Li, Minming Li, Xiaowei Wu
In the online load balancing problem on related machines, we have a set of jobs (with different sizes) arriving online, and we need to assign each job to a machine immediately upon…
Towards a Better Understanding of Randomized Greedy Matching
Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang
There has been a long history for studying randomized greedy matching algorithms since the work by Dyer and Frieze~(RSA 1991). We follow this trend and consider the problem formula…
Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model
Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang +3
Huang et al.~(STOC 2018) introduced the fully online matching problem, a generalization of the classic online bipartite matching problem in that it allows all vertices to arrive on…