TY - GEN

T1 - Threshold Testing and Semi-Online Prophet Inequalities

AU - Hoefer, Martin

AU - Schewior, Kevin

N1 - Funding Information:
Funding Martin Hoefer: Supported by DFG Research Unit ADYN (411362735) and grant 514505843. Kevin Schewior: Supported by the Independent Research Fund Denmark, Natural Sciences, grant DFF-0135-00018B.

PY - 2023/9

Y1 - 2023/9

N2 - 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).

AB - 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).

KW - Prophet Inequalities

KW - Stochastic Probing

KW - Testing

U2 - 10.4230/LIPIcs.ESA.2023.62

DO - 10.4230/LIPIcs.ESA.2023.62

M3 - Article in proceedings

AN - SCOPUS:85173470643

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 31st Annual European Symposium on Algorithms, ESA 2023

A2 - Li Gortz, Inge

A2 - Farach-Colton, Martin

A2 - Puglisi, Simon J.

A2 - Herman, Grzegorz

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 31st Annual European Symposium on Algorithms, ESA 2023

Y2 - 4 September 2023 through 6 September 2023

ER -