Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
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 (in compact repr…
cs.DS2022
Simple Algorithms for Stochastic Score Classification with Small Approximation Ratios
Benedikt M. Plank, Kevin Schewior
We revisit the Stochastic Score Classification (SSC) problem introduced by Gkenosis et al. (ESA 2018): We are given tests. Each test can be conducted at cost , and it…