Abstract
Let M(d, n) denote the minimax number of group tests required for the identification of the d defectives in a set of n items. It was conjectured by Hu, Hwang and Wang that M(d, n) = n - 1 for n ≤ 3d, a surprisingly difficult combinatorial problem with very little known. The best known result is M(d, n) = n - 1 for n ≤ 42/16d by Du and Hwang. In this note we improve their result by proving M(d, n) = n - 1 for d ≥ 193 and n ≤ 43/16d.
Original language | English |
---|---|
Pages (from-to) | 29-32 |
Number of pages | 4 |
Journal | Ars Combinatoria |
Volume | 64 |
State | Published - Jul 2002 |
Keywords
- Group testing