Abstract: In submodular covering problems, we are given a monotone, nonnegative

submodular function f and wish to find the min-cost subset S of N such

that f(S) = f(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_{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(cmax /

cmin)*\sum_{t \leq T} g_t(N), where c_max, c_min are the

largest/smallest costs of elements in 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 submodular functions that

also have positive mixed third derivatives, we show an optimal recourse

bound of O(\sum_{t \leq T} g_t(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.

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.

Joint work with Anupam Gupta.