A new adaptive algorithm for competitive group testing

In the context of fault-detection problems, the objective is to identify all defective items among a set of n binary-state items using the minimum number of tests. The group testing paradigm, which allows testing a subset of items in a single test, serves as a fundamental technique for efficiently classifying large populations. We study a central problem in the combinatorial group testing model where the number d of defective items is unknown in advance. Let Mα(d|n) denote the maximum number of tests required by an algorithm α for this problem, and M(d, n) denote the minimum number of tests required in the worst case when d is known in advance. An algorithm α is called a c-competitive algorithm if there exist constants c and a such that, for 0≤d<n, Mα(d|n)≤cM(d,n)+a. We develop a modular two-stage framework for this problem: (i) a constant-size preliminary-testing stage that extracts coarse information about d; and (ii) a conditional invocation stage that, based on the preliminary outcome, invokes either our newly developed up-zig-zag approach or an existing strongly competitive algorithm. With carefully designed switching rules, this framework yields a deterministic adaptive algorithm with a competitive ratio c≤1.431, improving the previous best-known bound of 1.452. This guarantee is achieved via a reusable integration principle that combines a constant preliminary overhead with a second-stage choice tailored to the remaining uncertainty.