2013/10/16 by Marek Adamczyk, Adamczyk, Marek, Maxim Sviridenko +3 · 2 citations
Computer Science · Decision Sciences · #Auction Theory and Applications #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #cs.DS
paper · pdf · doi:10.48550/arxiv.1310.4415
openalex publication_date 2013/10/16 · arxiv created 2014/02/18 · arxiv updated 2014/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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.