Distributionally Robust $k$-of-$n$ Sequential Testing
This work addresses a limitation in stochastic optimization for testing problems, offering robust solutions for scenarios with uncertain probabilities, though it is incremental in extending existing models.
The paper tackles the problem of sequential testing where test probabilities are uncertain by introducing a distributionally-robust model, and it provides approximation algorithms with specific bounds, such as a 2-approximation for unit costs and an O(1/√ε)-approximation for general costs on ε-bounded instances.
The $k$-of-$n$ testing problem involves performing $n$ independent tests sequentially, in order to determine whether/not at least $k$ tests pass. The objective is to minimize the expected cost of testing. This is a fundamental and well-studied stochastic optimization problem. However, a key limitation of this model is that the success/failure probability of each test is assumed to be known precisely. In this paper, we relax this assumption and study a distributionally-robust model for $k$-of-$n$ testing. In our setting, each test is associated with an interval that contains its (unknown) failure probability. The goal is to find a solution that minimizes the worst-case expected cost, where each test's probability is chosen from its interval. We focus on non-adaptive solutions, that are specified by a fixed permutation of the tests. When all test costs are unit, we obtain a $2$-approximation algorithm for distributionally-robust $k$-of-$n$ testing. For general costs, we obtain an $O(\frac{1}{\sqrt ε})$-approximation algorithm on $ε$-bounded instances where each uncertainty interval is contained in $[ε, 1-ε]$. We also consider the inner maximization problem for distributionally-robust $k$-of-$n$: this involves finding the worst-case probabilities from the uncertainty intervals for a given solution. For this problem, in addition to the above approximation ratios, we obtain a quasi-polynomial time approximation scheme under the assumption that all costs are polynomially bounded.