Dipartimento di Matematica Guido Castelnuovo, Sapienza Università di Roma
Yaakov Malinovsky (University of Maryland, Baltimore County)
Group testing has its origins in the identication of syphilis in the US army during World War II. It is a useful method that has broad applications in medicine, engineering, and even in airport security control. Consider a finite population of N units, where unit i has a probability p to be defective. A group test is a simultaneous test on an arbitrary group of units with two possible outcomes: all units are good or at least one of the units is defective. The goal is to construct a procedure which classifies all units in a given population, with as small as possible expected number of tests. In this talk I shall review previously known results in the group testing literature and present new results characterizing optimality of commonly used nested group testing procedures. In the second part of the talk, the generalized group testing problem (where unit i has a probability p_{i} to be defective) will be discussed as well.