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 $2$ against an oblivious adversary, even on bipartite graphs. Since the standard algorithm that takes both endpoints of every uncovered edge is $2...
Online resource-allocation systems, like outpatient scheduling and spectrum allocation, often assign sequentially arriving requests to an ordered pool of scarce resources, where each request accepts a contiguous interval of feasible options. We study the resulting online matching problem on convex bipartite graphs unde...
Yi-Long Feng, Zhihao Gavin Tang, Kang-Ning Wang et al.· 0 citations
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 limited time, and extends the classic Water-Filling algorithm to the fully online setting, establishing that Water-Filling is not optimal in...
