The online submodular cover problem

Anupam Gupta, Roie Levin

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

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) = Pst gs 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 St1 ⊆ 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(ln n ln(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. [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.

Original languageEnglish (US)
Title of host publication31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
EditorsShuchi Chawla
PublisherAssociation for Computing Machinery
Pages1525-1537
Number of pages13
ISBN (Electronic)9781611975994
StatePublished - 2020
Event31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 - Salt Lake City, United States
Duration: Jan 5 2020Jan 8 2020

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2020-January

Conference

Conference31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
Country/TerritoryUnited States
CitySalt Lake City
Period1/5/201/8/20

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'The online submodular cover problem'. Together they form a unique fingerprint.

Cite this