Online Rounding Schemes for Edge Cover

Abstract

Linear programming rounding is a fundamental technique in the design of approximation and online algorithms. A growing body of work has investigated online rounding schemes for various combinatorial optimization problems, with applications including multi-stage stochastic optimization. More recently, Naor, Srinivasan, and Wajc (SODA 2025) study online rounding for bipartite (b-)matching and achieve a rounding factor better than 1 - 1/e. Motivated by this line of research, we study online rounding schemes for the edge cover problem. Our main contribution is a 1.8-competitive online rounding scheme for general (possibly non-bipartite) graphs. The key idea is to incorporate a controlled form of adaptivity based on the coverage status of endpoints, while guaranteeing both upper and lower bounds on the probability that each edge is selected. We further obtain an improved (1 + 1/e)-competitive online rounding scheme for bipartite graphs under a model in which all edges incident to an ``online'' vertex are revealed simultaneously in each round. Finally, we establish lower bounds on the competitive ratio for bipartite graphs, demonstrating a strict separation between offline and online rounding schemes.

Appeared in WAOA 2026. Through a review process, it turned out that a folklore offline rounding scheme can be adapted to an O(log s)-competitive online rounding scheme for general set cover under subset arrivals. There was a gap in the analysis in an earlier version, which has been fixed in this version