3 papers
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.DS2025
Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid
Haya Diwan, Lisa Hellerstein, Nicole Megow +1
Research in explorable uncertainty addresses combinatorial optimization problems where there is partial information about the values of numeric input parameters, and exact values o…
cs.DS2024
Quickly Determining Who Won an Election
Lisa Hellerstein, Naifeng Liu, Kevin Schewior
This paper considers elections in which voters choose one candidate each, independently according to known probability distributions. A candidate receiving a strict majority (absol…