5 citations · 17 across the 10 of their papers we have counts for
Showing 2026Show all
2 papers · 1 filter
cs.DS2026
A Tight Bound on Online Vertex Cover under Edge Arrivals
Zhihao Gavin Tang, Yuhao Zhang
We prove a tight impossibility result for online vertex cover under edge arrivals. No randomized integral or fractional algorithm achieves a competitive ratio strictly below ag…
cs.DS2026
Fractional Fully Online Matching
Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu +1
This paper studies fractional matching on general graphs in the fully online model of Huang et al. (JACM 2020), in which all vertices arrive online and remain available for only a…