## Abstract

In the submodular cover problem, we are given a monotone submodular function f : 2^{N} → 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 g_{t} is given to us. We define f^{(}t^{)} = ^{P}_{s}≤_{t} g_{s} 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 S_{t} ⊆ N such that f^{(}t^{)}(S_{t}) = f^{(}t^{)}(N)-i.e., this set S_{t} is a cover-such that S_{t}−_{1} ⊆ S_{t}, 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 · f_{max}/f_{min})), where f_{max} and f_{min} 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 language | English (US) |
---|---|

Title of host publication | 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 |

Editors | Shuchi Chawla |

Publisher | Association for Computing Machinery |

Pages | 1525-1537 |

Number of pages | 13 |

ISBN (Electronic) | 9781611975994 |

State | Published - 2020 |

Event | 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 - Salt Lake City, United States Duration: Jan 5 2020 → Jan 8 2020 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Volume | 2020-January |

### Conference

Conference | 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 |
---|---|

Country/Territory | United States |

City | Salt Lake City |

Period | 1/5/20 → 1/8/20 |

## ASJC Scopus subject areas

- Software
- General Mathematics