Fully-dynamic submodular cover with bounded recourse

In submodular covering problems, we are given a monotone, nonnegative submodular function f:2{mathcal{N}} rightarrow mathbb{R} {+} and wish to find the min-cost set S subseteq mathcal{N} such that f(S)=f(mathcal{N}). When f is a coverage function, this captures Setcover as a special case. We introduce a general framework for solving such problems in a fully-dynamic setting where the function f changes over time, and only a bounded number of updates to the solution (a.k.a. recourse) is allowed. For concreteness, suppose a nonnegative monotone submodular integer-valued function g {t} is added or removed from an active set G{(t)} at each time t. If f{(t)}= sum nolimits {g in G{(t)}}g is the sum of all active functions, we wish to maintain a competitive solution to Submodularcover for f{(t)} as this active set changes, and with low recourse. For example, if each g {t} is the (weighted) rank function of a matroid, we would be dynamically maintaining a low-cost common spanning set for a changing collection of matroids. We give an algorithm that maintains an O(log(f {max}/f {min}))-competitive solution, where f {max}, f {min} are the largest/smallest marginals of f{(t)}. The algorithm guarantees a total recourse of O(log(c {max}/c {min}) cdot sum nolimits {t < T}g {t}(mathcal{N})), where c {min}, c {min} are the largest/smallest costs of elements in mathcal{N}. This competitive ratio is best possible even in the offline setting, and the recourse bound is optimal up to the logarithmic factor. For monotone sub-modular functions that also have positive mixed third derivatives, we show an optimal recourse bound of O(sum nolimits {t < T}g {t}(mathcal{N})). This structured class includes set-coverage functions, so our algorithm matches the known O(log n)-competitiveness and O(1) recourse guarantees for fully-dynamic Setcover. Our work simultaneously simplifies and unifies previous results, as well as generalizes to a significantly larger class of covering problems. Our key technique is a new potential function inspired by Tsallis entropy. We also extensively use the idea of Mutual Coverage, which generalizes the classic notion of mutual information.