  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 $\tau$. 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 <
\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 \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.

Data Structures and Algorithms