Threshold Testing and Semi-Online Prophet Inequalities

Martin Hoefer, Kevin Schewior

We study threshold testing, an elementary probing model with the goal to choose a large value out of $n$ i.i.d. random variables. An algorithm can test each variable $X_i$ once for…