Аннотация:
Group testing is a well-known search problem that consists in detecting of s defective members in a set of t elements by carrying out tests on properly chosen subsets. A test result is positive if there is at least one defective element in a tested subset; otherwise, the result is negative. Our goal is to find all defective elements by using the minimal possible number of tests in the worst case.
Two types of algorithms are usually considered in group testing. Adaptive algorithms can use results of previous tests to determine which subset of samples to test at the next step. In non-adaptive algorithms all tests are predetermined and can be carried out in parallel.
We consider multistage algorithms, which can be seen as a compromise solution to the group testing problem. The advantage of this approach is that we can greatly reduce the total number of tests, but still perform a lot of them in parallel. Our general goal is to construct a multistage search procedure, having asymptotically the same number of tests as an adaptive one. We propose such algorithms for s=2,3.
