The Optimality of a Nested Generalized Pairwise Group Testing Procedure

We study the problem of identifying defective units in a finite population of $n$ units, where each unit $i$ is independently defective with known probability $p_i$. This setting is referred to as the \emph{Generalized Group Testing Problem}. A testing procedure is called optimal if it minimizes the expected number of tests. It has been conjectured that, when all probabilities $p_i$ lie within the interval $[1-\frac{1}{\sqrt{2}},\frac{3-\sqrt{5}}{2}]$, the \emph{generalized pairwise testing {algorithm}}, applied to the $p_i$ arranged in nondecreasing order, constitutes the optimal nested testing strategy among all such order-preserving nested strategies. In this work, we confirm this conjecture and establish the optimality of the procedure within the specified regime. Additionally, we provide a complete structural characterization of the procedure and derive a closed-form expression for its expected number of tests. These results offer new insights into the theory of optimal nested strategies in generalized group testing.