On optimal randomized group testing with one defective item and a constrained number of positive responses

Abstract Consider the group testing problem with an input set of size n and the number of defective items being d = 1 , that allows at most y positive responses. Let A n , y denote the minimum expected number of tests required by a randomized testing strategy for this problem. The testing strategy is required to be Las Vagas, that is, guaranteed to give the correct classification of the items. Based on Yao’s minimax principle, A n , y is equal to the minimum average number of tests for a deterministic group testing strategy allowing at most y positive responses, where the average is taken over all the n possible input sets of size n with d = 1 . The main contribution of our paper is to show that A n , y is y y + 1 ( n y ! ) 1 y + O ( y ) , for 1 ≤ y ⌈ log 2 n ⌉ . This solves an open question left in Damaschke (2016).