
doi: 10.1137/0602011
A previous result [F. K. Hwang, Tamkang J. Math., 2 (1971), pp. 39–44] showed that a minimax group testing algorithm to find d defectives in n items is to test each item individually for $d\geqq 0.5n$. In this paper we improve this result by proving that individual testing is minimax for $d\geqq 0.4n$. We also conjecture that the same is true for $d\geqq \frac{1}{3}n$. On the other hand, we prove that individual testing is not minimax for $d < \frac{1}{3}n$.
minimax group testing algorithm, Exact enumeration problems, generating functions, Trees
minimax group testing algorithm, Exact enumeration problems, generating functions, Trees
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 24 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
