Theory Lunch Seminar

Wednesday, September 25, 2019 - 12:00pm to 1:00pm


ASA Conference Room 6115 Gates Hillman Centers


ROIE LEVIN, Ph.D. Student

The Online Submodular Cover Problem

See website for accurate abstract:

In the submodular cover problem, we are given a monotone submodular function f:2N→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 gt is given to us. We define f(t)=∑s≤tgs as the sum of all functions seen so far. We need to maintain a submodular cover of these submodular functions f(1),f(2),…f(T) in an online fashion; i.e., we cannot revoke previous choices. Formally, at each time t we produce a set St⊆N such that f(t)(St)=f(t)(N)---i.e., this set St is a cover---such that St−1⊆St, 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(lnnln(T⋅fmax/fmin)), where fmax and fmin 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⊆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.

Event Website:

For More Information, Contact:


Seminar Series