# Scalable Bicriteria Algorithms for Non-Monotone Submodular Cover

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Dec 2021.

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

- [A Dynamic Algorithm for Weighted Submodular Cover Problem](https://mlsanity.com/paper/2407.10003/) (2024)

## Abstract (arXiv)

In this paper, we consider the optimization problem scpl (scp), which is to find a minimum cost subset of a ground set U such that the value of a submodular function f is above a threshold τ. In contrast to most existing work on scp, it is not assumed that f is monotone. Two bicriteria approximation algorithms are presented for scp that, for input parameter 0 < ε < 1, give O( 1 / ε2 ) ratio to the optimal cost and ensures the function f is at least τ(1 - ε)/2. A lower bound shows that under the value query model shows that no polynomial-time algorithm can ensure that f is larger than τ/2. Further, the algorithms presented are scalable to large data sets, processing the ground set in a stream. Similar algorithms developed for scp also work for the related optimization problem of smpl (smp). Finally, the algorithms are demonstrated to be effective in experiments involving graph cut and data summarization functions.