The Optimality of a Nested Generalized Pairwise Group Testing Procedure

Abstract

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ᵢ. This setting is referred to as the 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ᵢ lie within the interval [ (1 - (1 / √2)) , ((3 - √5) / 2) ], the generalized pairwise testing algorithm, applied to the pᵢ 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.