2026-07-20T09:02:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23385 2025-10-02T12:53:40Z ddc:004 open_access

Identifying Approximate Minimizers Under Stochastic Uncertainity Al-Thani, Hessa Nagarajan, Viswanath Approximation algorithms stochastic optimization selection problem We study a fundamental stochastic selection problem involving n independent random variables, each of which can be queried at some cost. Given a tolerance level δ, the goal is to find a δ-approximately minimum (or maximum) value over all the random variables, at minimum expected cost. A solution to this problem is an adaptive sequence of queries, where the choice of the next query may depend on previously-observed values. Two variants arise, depending on whether the goal is to find a δ-minimum value or a δ-minimizer. When all query costs are uniform, we provide a 4-approximation algorithm for both variants. When query costs are non-uniform, we provide a 5.83-approximation algorithm for the δ-minimum value and a 7.47-approximation for the δ-minimizer. All our algorithms rely on non-adaptive policies (that perform a fixed sequence of queries), so we also upper bound the corresponding "adaptivity" gaps. Our analysis relates the stopping probabilities in the algorithm and optimal policies, where a key step is in proving and using certain stochastic dominance properties. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hessa Al-Thani and Viswanath Nagarajan 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.8 urn:nbn:de:0030-drops-233854 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.8 eng https://creativecommons.org/licenses/by/4.0/legalcode