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

Lisa Hellerstein, Benedikt M. Plank, Kevin Schewior

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 repr…