Abstract
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 some threshold t_i, and the test returns binary feedback whether X_i ≥ t_i or not. Thresholds can be chosen adaptively or nonadaptively by the algorithm. Given the results for the tests of each variable, we then select the variable with highest conditional expectation. We compare the expected value obtained by the testing algorithm with expected maximum of the variables.
Threshold testing is a semionline variant of the gambler’s problem and prophet inequalities. Indeed, the optimal performance of nonadaptive algorithms for threshold testing is governed by the standard i.i.d. prophet inequality of approximately 0.745 + o(1) as n → ∞. We show how adaptive algorithms can significantly improve upon this ratio. Our adaptive testing strategy guarantees a competitive ratio of at least 0.869  o(1). Moreover, we show that there are distributions that admit only a constant ratio c < 1, even when n → ∞. Finally, when each box can be tested multiple times (with n tests in total), we design an algorithm that achieves a ratio of 1  o(1).
BibTeX  Entry
@InProceedings{hoefer_et_al:LIPIcs.ESA.2023.62,
author = {Hoefer, Martin and Schewior, Kevin},
title = {{Threshold Testing and SemiOnline Prophet Inequalities}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {62:162:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772952},
ISSN = {18688969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and FarachColton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18715},
URN = {urn:nbn:de:0030drops187159},
doi = {10.4230/LIPIcs.ESA.2023.62},
annote = {Keywords: Prophet Inequalities, Testing, Stochastic Probing}
}
Keywords: 

Prophet Inequalities, Testing, Stochastic Probing 
Collection: 

31st Annual European Symposium on Algorithms (ESA 2023) 
Issue Date: 

2023 
Date of publication: 

30.08.2023 