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.

The NP-hard maximum-entropy sampling problem (MESP) seeks a maximum (log-)determinant principal submatrix, of a given order, from a positive-semidefinite input matrix C. We give an efficient dynamic-programming algorithm for MESP when C (or its inverse) is tridiagonal. A mask M for MESP is a correlation matrix with which we pre-process C, by taking the Hadamard product M ◦C. Upper bounds on MESP with M ◦C give upper bounds on MESP with C. Most upper-bounding methods are much faster to apply, when the input matrix is tridiagonal, so we consider tridiagonal masks M (which yield tridiagonal M ◦ C). We analyze such tridiagonal masks, and develop a combinatorial local-search based upper-bounding method that takes advantage of fast computations on tridiagonal matrices.