# A Dynamic Algorithm for Weighted Submodular Cover Problem

arXiv: https://arxiv.org/abs/2407.10003 · HTML: https://mlsanity.com/paper/2407.10003/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 27 references that are in the map.
- First posted on arXiv 13 Jul 2024.

## Builds on (most cited first, 17 of 17)

- [Randomized Composable Core-sets for Distributed Submodular Maximization](https://mlsanity.com/paper/1506.06715/) (2015)
- [Submodular Maximization Meets Streaming: Matchings, Matroids, and More](https://mlsanity.com/paper/1309.2038/) (2013)
- [Streaming Non-monotone Submodular Maximization: Personalized Video Summarization on the Fly](https://mlsanity.com/paper/1706.03583/) (2017)
- [Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity](https://mlsanity.com/paper/1905.00948/) (2019)
- [Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams](https://mlsanity.com/paper/1808.01842/) (2018)
- [Fully Dynamic Algorithm for Constrained Submodular Optimization](https://mlsanity.com/paper/2006.04704/) (2020)
- [Submodular Optimization in the MapReduce Model](https://mlsanity.com/paper/1810.01489/) (2018)
- [Deletion Robust Submodular Maximization over Matroids](https://mlsanity.com/paper/2201.13128/) (2022)
- [Fully Dynamic Submodular Maximization over Matroids](https://mlsanity.com/paper/2305.19918/) (2023)
- [Dynamic Algorithms for Matroid Submodular Maximization](https://mlsanity.com/paper/2306.00959/) (2023)
- [Bicriteria Approximation Algorithms for the Submodular Cover Problem](https://mlsanity.com/paper/2309.14558/) (2023)
- [On the Complexity of Dynamic Submodular Maximization](https://mlsanity.com/paper/2111.03198/) (2021)
- [Dynamic Constrained Submodular Optimization with Polylogarithmic Update Time](https://mlsanity.com/paper/2305.15192/) (2023)
- [An Efficient Streaming Algorithm for the Submodular Cover Problem](https://mlsanity.com/paper/1611.08574/) (2016)
- [Fully-Dynamic Submodular Cover with Bounded Recourse](https://mlsanity.com/paper/2009.00800/) (2020)
- [Scalable Bicriteria Algorithms for Non-Monotone Submodular Cover](https://mlsanity.com/paper/2112.09985/) (2021)
- [Dynamic Non-monotone Submodular Maximization](https://mlsanity.com/paper/2311.03685/) (2023)

## Abstract (arXiv)

We initiate the study of the submodular cover problem in dynamic setting where the elements of the ground set are inserted and deleted. In the classical submodular cover problem, we are given a monotone submodular function f : 2V → ℝ≥ 0 and the goal is to obtain a set S subseteq V that minimizes the cost subject to the constraint f(S) = f(V). This is a classical problem in computer science and generalizes the Set Cover problem, 2-Set Cover, and dominating set problem among others. We consider this problem in a dynamic setting where there are updates to our set V, in the form of insertions and deletions of elements from a ground set V, and the goal is to maintain an approximately optimal solution with low query complexity per update. For this problem, we propose a randomized algorithm that, in expectation, obtains a (1-O(ε), O(ε-1))-bicriteria approximation using polylogarithmic query complexity per update.