# Submodular Cost Submodular Cover with an Approximate Oracle

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Aug 2019.

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

- [Robust Counterfactual Explanations on Graph Neural Networks](https://mlsanity.com/paper/2107.04086/) (2021)
- [Finding Representative Interpretations on Convolutional Neural Networks](https://mlsanity.com/paper/2108.06384/) (2021)
- [Mini-batch Submodular Maximization](https://mlsanity.com/paper/2401.12478/) (2024)
- [Linear Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2407.02601/) (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)
- [Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint](https://mlsanity.com/paper/2511.02254/) (2025)

## Abstract (arXiv)

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.