Paper Info
Title
Hypergeometric group testing algorithms
Abstract
Given a finite population P consisting of g good and d defective objects, the problems of hypergeometric group testing (HGT) is concerned with the identification of the d defectives by means of the following test procedure. Any subset X⊂P can be tested with two possible results: (1) either all elements of X are good, or (2) at least one element of X is defective. In the latter case, we have no knowledge as to which ones or how many are defective. In recent years, various algorithms have been proposed to solve this problem with the aim of minimizing the maximum number of tests required. However, no optimal algorithm is known at present for general g and d 1. We define an algorithm s to solve the HGT problem to be an l-set algorithm if throughout the entire process of implementing s, we only need to partition the still unclassified elements of P into at most l sets (P1. ... Pl) where objects in each Pi need not be differentiated from one another. Restricting s to be an l-set algorithm limits the range of useful tests we can make as the amount of information we can keep after each successive tests depends on l. We show that all previously known HGT algorithms are either 1 or 2-set algorithms. By increasing l, we are able to construct some new classes of HGT algorithms which are more efficient than all previously known algorithms. Finally, we are able to construct optimal HGT algorithms for l≤3.
Year
DOI
Venue
1973
10.1145/1499586.1499700
AFIPS National Computer Conference
Keywords
Field
DocType
l-set algorithm,hgt algorithm,2-set algorithm,optimal hgt algorithm,l set,hypergeometric group testing algorithm,various algorithm,optimal algorithm,finite population p,defective object,hgt problem,group testing
Population,Hypergeometric distribution,Computer science,Algorithm,Partition (number theory),Group testing,Test procedures
Conference
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
F. K. Hwang1332100.54
S. Lin221.12