{"ID":2857243,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.08883","arxiv_id":"2510.08883","title":"The Online Submodular Cover Problem","abstract":"In the submodular cover problem, we are given a monotone submodular function $f$, and we want to pick the min-cost set $S$ such that $f(S) = f(N)$. Motivated by problems in network monitoring and resource allocation, we consider the submodular cover problem in an online setting. As a concrete example, suppose at each time $t$, a nonnegative monotone submodular function $g_t$ is given to us. We define $f^{(t)} = \\sum_{s \\leq t} g_s$ as the sum of all functions seen so far. We need to maintain a submodular cover of these submodular functions $f^{(1)}, f^{(2)}, \\ldots f^{(T)}$ in an online fashion; i.e., we cannot revoke previous choices. Formally, at each time $t$ we produce a set $S_t \\subseteq N$ such that $f^{(t)}(S_t) = f^{(t)}(N)$ -- i.e., this set $S_t$ is a cover -- such that $S_{t-1} \\subseteq S_t$, so previously decisions to pick elements cannot be revoked. (We actually allow more general sequences $\\{f^{(t)}\\}$ of submodular functions, but this sum-of-simpler-submodular-functions case is useful for concreteness.) We give polylogarithmic competitive algorithms for this online submodular cover problem. The competitive ratio on an input sequence of length $T$ is $O(\\ln n \\ln (T \\cdot f(N) / f_{\\text{min}}))$, where $f_{\\text{min}}$ is the smallest nonzero marginal for functions $f^{(t)}$, and $|N| = n$. For the special case of online set cover, our competitive ratio matches that of Alon et al. [SIAM J. Comp. 03], which are best possible for polynomial-time online algorithms unless $NP \\subseteq BPP$ (see Korman 04). Since existing offline algorithms for submodular cover are based on greedy approaches which seem difficult to implement online, the technical challenge is to (approximately) solve the exponential-sized linear programming relaxation for submodular cover, and to round it, both in the online setting.","short_abstract":"In the submodular cover problem, we are given a monotone submodular function $f$, and we want to pick the min-cost set $S$ such that $f(S) = f(N)$. Motivated by problems in network monitoring and resource allocation, we consider the submodular cover problem in an online setting. As a concrete example, suppose at each t...","url_abs":"https://arxiv.org/abs/2510.08883","url_pdf":"https://arxiv.org/pdf/2510.08883v1","authors":"[\"Anupam Gupta\",\"Roie Levin\"]","published":"2025-10-10T00:29:14Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}