Threshold Testing and Semi-Online Prophet Inequalities

Martin Hoefer*, Kevin Schewior*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

50 Downloads (Pure)


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 Xi once for some threshold ti, and the test returns binary feedback whether Xi ≥ ti or not. Thresholds can be chosen adaptively or non-adaptively 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 semi-online variant of the gambler’s problem and prophet inequalities. Indeed, the optimal performance of non-adaptive 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).

Original languageEnglish
Title of host publication31st Annual European Symposium on Algorithms, ESA 2023
EditorsInge Li Gortz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman
Number of pages15
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication dateSept 2023
Article number62
ISBN (Electronic)9783959772952
Publication statusPublished - Sept 2023
Event31st Annual European Symposium on Algorithms, ESA 2023 - Amsterdam, Netherlands
Duration: 4. Sept 20236. Sept 2023


Conference31st Annual European Symposium on Algorithms, ESA 2023
SeriesLeibniz International Proceedings in Informatics, LIPIcs


  • Prophet Inequalities
  • Stochastic Probing
  • Testing


Dive into the research topics of 'Threshold Testing and Semi-Online Prophet Inequalities'. Together they form a unique fingerprint.

Cite this