{"id":"arxiv/2608.09210","url":"https://arxiv.org/abs/2608.09210","tags":["cs.DS","cs.GT","math.OC"],"score":0,"title":"A New Lower Bound for Online Vertex Cover under Vertex Arrivals","domain":"cs.DS","source":"arxiv","authors":["Tianhang Lu"],"reviews":0,"subject":"cs.DS","summary":"We prove that no randomized integral or fractional algorithm for online vertex cover under general vertex arrivals achieves a competitive ratio strictly below $1+\\sqrt{e}/2\\approx1.824360635$, even on bipartite graphs and against an oblivious adversary. This improves the previous lower bound of approximately $1.753$. Our proof extends the complete-bipartite alternating construction of Wang and Wong to an arbitrary number of alternations. The resulting adversary is described by a monotone integral recurrence. If the recurrence never violates the competitive budget, its iterates converge to an…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-10","reactions":{}}