  In this work, we study the Submodular Cost Submodular Cover problem, which is
to minimize the submodular cost required to ensure that the submodular benefit
function exceeds a given threshold. Existing approximation ratios for the
greedy algorithm assume a value oracle to the benefit function. However, access
to a value oracle is not a realistic assumption for many applications of this
problem, where the benefit function is difficult to compute. We present two
incomparable approximation ratios for this problem with an approximate value
oracle and demonstrate that the ratios take on empirically relevant values
through a case study with the Influence Threshold problem in online social
networks.
