# Submodular Stochastic Probing on Matroids

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

## Key facts

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

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

- [Online Learning for Min Sum Set Cover and Pandora's Box](https://mlsanity.com/paper/2202.04870/) (2022)
- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [Contextual Pandora's Box](https://mlsanity.com/paper/2205.13114/) (2022)
- [Minimum Cost Adaptive Submodular Cover](https://mlsanity.com/paper/2208.08351/) (2022)
- [Approximating Pandora's Box with Correlations](https://mlsanity.com/paper/2108.12976/) (2021)
- [Constrained Stochastic Submodular Maximization with State-Dependent Costs](https://mlsanity.com/paper/2111.06037/) (2021)
- [T-TAMER: Provably Taming Trade-offs in ML Serving](https://mlsanity.com/paper/2509.22992/) (2025)

## Abstract (arXiv)

In a stochastic probing problem we are given a universe E, where each element e ∈ E is active independently with probability pe, and only a probe of e can tell us whether it is active or not. On this universe we execute a process that one by one probes elements --- if a probed element is active, then we have to include it in the solution, which we gradually construct. Throughout the process we need to obey inner constraints on the set of elements taken into the solution, and outer constraints on the set of all probed elements. This abstract model was presented by Gupta and Nagarajan (IPCO '13), and provides a unified view of a number of problems. Thus far, all the results falling under this general framework pertain mainly to the case in which we are maximizing a linear objective function of the successfully probed elements. In this paper we generalize the stochastic probing problem by considering a monotone submodular objective function. We give a (1 - 1/e)/(kin + kout+1)-approximation algorithm for the case in which we are given kin matroids as inner constraints and kout matroids as outer constraints. Additionally, we obtain an improved 1/(kin + kout)-approximation algorithm for linear objective functions.