Scalable Bicriteria Algorithms for Non-Monotone Submodular Cover

Abstract

In this paper, we consider the optimization problem Submodular Cover (SC), 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 $\tau$. In contrast to most existing work on SC, it is not assumed that $f$ is monotone. Two bicriteria approximation algorithms are presented for SC that, for input parameter $0 < \epsilon < 1$, give $O( 1 / \epsilon^2 )$ ratio to the optimal cost and ensures the function $f$ is at least $\tau(1 - \epsilon)/2$. A lower bound shows that under the value query model shows that no polynomial-time algorithm can ensure that $f$ is larger than $\tau/2$. Further, the algorithms presented are scalable to large data sets, processing the ground set in a stream. Similar algorithms developed for SC also work for the related optimization problem of Submodular Maximization (KCSM). Finally, the algorithms are demonstrated to be effective in experiments involving graph cut and data summarization functions.