Approximating Matroid Basis Testing for Partition Matroids using Budget-In-Expectation

We consider the following Stochastic Boolean Function Evaluation problem, which is closely related to several problems from the literature. A matroid \(\mathcal{M}\) (in compact representation) on ground set \(E\) is given, and each element \(i \in E\) is active independently with known probability \(p_i \in (0,1)\). The elements can be queried, upon which it is revealed whether the respective element is active or not. The goal is to find an adaptive querying strategy for determining whether there is a basis of \(\mathcal{M}\) in which all elements are active, with the objective of minimizing the expected number of queries.