DocumentCode :
3356086
Title :
The capacity of adaptive group testing
Author :
Baldassini, Leonardo ; Johnson, O. ; Aldridge, Matthew
Author_Institution :
Sch. of Math., Univ. of Bristol, Bristol, UK
fYear :
2013
fDate :
7-12 July 2013
Firstpage :
2676
Lastpage :
2680
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on
Conference_Location :
Istanbul
ISSN :
2157-8095
Type :
conf
DOI :
10.1109/ISIT.2013.6620712
Filename :
6620712
Link To Document :
بازگشت