In the submodular cover problem, we are given a monotone submodular function $f: 2^N \to \mathbb{R}_+$, and we want to pick the min-cost set $S$ such that $f(S) = f(N)$. This captures the set cover problem when $f$ is a coverage function. 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_{\max} / f_{\min}))$, where $f_{\max}$ and $f_{\min}$ are the largest and smallest marginals for functions $f^{(t)}$, and $|N| = n$. For the special case of online set cover, our competitive ratio matches that of (Alon et al. 03), which are best possible for polynomial-time online algorithms unless $NP \subseteq BPP$ (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 Wolsey's exponential-sized linear programming relaxation for submodular cover, and to round it, both in the online setting. Moreover, to get our competitiveness bounds, we define a (seemingly new) generalization of mutual information to general submodular functions, which we call _mutual coverage_; we hope this will be useful in other contexts.

Joint work with Anupam Gupta.