Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-19T03:13:22.068Z Has data issue: false hasContentIssue false
  • English
  • Français

Individual Testing of Independent Items in Optimal Group Testing

Published online by Cambridge University Press:  27 July 2009

Y. C. Yao  and
F. K. Hwang
Y. C. Yao
Affiliation:
Department ofStatistics Colorado State University Fort Collins, Colorado 80523
F. K. Hwang
Affiliation:
Director of Discrete Mathematics AT&T Bell Laboratories Murray Hill, New Jersey 07974
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the group testing problem for a set of independent items I = [I1,… In] where Ii, has probability pi, of being defective and probability qi = 1 – pi of being good. The problem is to classify all items as good or defective with a minimum expected number of group tests where a group test is a test on a subset S of I with two possible outcomes: either S is pure (contains no defective) or S is contaminated (contains at least one defective, with no information provided about which or how many). No polynomial-time algorithm is known for the group testing problem even for the special case pi = p for all i. Hence, any method that reduces the size of the problem is very helpful. In this paper, we give such a method by providing a simple condition to screen items that should be tested (only) individually. This condition leads to a necessary and sufficient condition for the individual testing algorithm to be optimal, generalizing a result of Unger [1] for the special case of identical pi.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 2 , Issue 1 , January 1988 , pp. 23 - 29
Copyright
Copyright © Cambridge University Press 1988

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Unger, P. (1960). The cutoff point for group testing. Communication on Pure and Applied Mathematics 13: 49–54.CrossRefGoogle Scholar
Yao, Y.C. & Hwang, F.K., A fundamental monotonicity in group testing, to appear.Google Scholar