The capacity of non-identical adaptive group testing

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

9 Citations (Scopus)

Abstract

We consider the group testing problem, in the case where the items are defective independently but with non-constant probability. We introduce and analyse an algorithm to solve this problem by grouping items together appropriately. We give conditions under which the algorithm performs essentially optimally in the sense of information-theoretic capacity. We use concentration of measure results to bound the probability that this algorithm requires many more tests than the expected number. This has applications to the allocation of spectrum to cognitive radios, in the case where a database gives prior information that a particular band will be occupied.
Original languageUndefined/Unknown
Title of host publicationProceedings of the 52nd Annual Allerton Conference on Communication, Control and Computing
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages101-108
DOIs
Publication statusPublished - 1 Oct 2014

Cite this