Title :
The capacity of adaptive group testing
Author :
Baldassini, Leonardo ; Johnson, O. ; Aldridge, Matthew
Author_Institution :
Sch. of Math., Univ. of Bristol, Bristol, UK
Abstract :
We define capacity for group testing problems and deduce bounds for the capacity of a variety of noisy models, based on the capacity of equivalent noisy communication channels. For noiseless adaptive group testing we prove an information-theoretic lower bound which tightens a bound of Chan et al. This can be combined with a performance analysis of a version of Hwang´s adaptive group testing algorithm, in order to deduce the capacity of noiseless and erasure group testing models.
Keywords :
channel capacity; group theory; information theory; noise; adaptive group testing algorithm; equivalent noisy communication channels; erasure group testing models; information-theoretic lower bound; noiseless adaptive group testing; noisy models capacitty; performance analysis; Adaptation models; Algorithm design and analysis; Educational institutions; Information theory; Noise measurement; Testing; Upper bound;
Conference_Titel :
Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on
Conference_Location :
Istanbul
DOI :
10.1109/ISIT.2013.6620712