# Bicriteria Approximation Algorithms for the Submodular Cover Problem

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Sep 2023.

## Built on by (most cited first, 6 of 6)

- [Fair Submodular Cover](https://mlsanity.com/paper/2407.04804/) (2024)
- [TimePre: Bridging Accuracy, Efficiency, and Stability in Probabilistic Time-Series Forecasting](https://mlsanity.com/paper/2511.18539/) (2025)
- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)
- [A Dynamic Algorithm for Weighted Submodular Cover Problem](https://mlsanity.com/paper/2407.10003/) (2024)
- [A Resilience Framework for Bi-Criteria Combinatorial Optimization with Bandit Feedback](https://mlsanity.com/paper/2503.12285/) (2025)
- [Fast Stochastic Greedy Algorithm for k-Submodular Cover Problem](https://mlsanity.com/paper/2511.00869/) (2025)

## Abstract (arXiv)

In this paper, we consider the optimization problem Submodular Cover (SCP), which is to find a minimum cardinality subset of a finite universe U such that the value of a submodular function f is above an input threshold τ. In particular, we consider several variants of SCP including the general case, the case where f is additionally assumed to be monotone, and finally the case where f is a regularized monotone submodular function. Our most significant contributions are that: (i) We propose a scalable algorithm for monotone SCP that achieves nearly the same approximation guarantees as the standard greedy algorithm in significantly faster time; (ii) We are the first to develop an algorithm for general SCP that achieves a solution arbitrarily close to being feasible; and finally (iii) we are the first to develop algorithms for regularized SCP. Our algorithms are then demonstrated to be effective in an extensive experimental section on data summarization and graph cut, two applications of SCP.