The online submodular cover problem

In the submodular cover problem, we are given a monotone submodular function f : 2^N → 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⁾ = ^P_s≤_t g_s as the sum of all functions seen so far. We need to maintain a submodular cover of these submodular functions f⁽¹⁾, f⁽²⁾, . . . f⁽T⁾ in an online fashion; i.e., we cannot revoke previous choices. Formally, at each time t we produce a set S_t ⊆ N such that f⁽t⁾(S_t) = f⁽t⁾(N)-i.e., this set S_t is a cover-such that S_t−₁ ⊆ 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 · 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. [AAA⁺09], which are best possible for polynomial-time online algorithms unless NP ⊆ BPP [Kor04]. 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. 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.