Fully-dynamic submodular cover with bounded recourse

Anupam Gupta, Roie Levin

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationProceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020
PublisherIEEE Computer Society
Number of pages11
ISBN (Electronic)9781728196213
StatePublished - Nov 2020
Event61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 - Virtual, Durham, United States
Duration: Nov 16 2020Nov 19 2020

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428


Conference61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020
Country/TerritoryUnited States
CityVirtual, Durham


  • dynamic algorithms
  • online algorithms
  • submodular optimization

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'Fully-dynamic submodular cover with bounded recourse'. Together they form a unique fingerprint.

Cite this