標題: | When is individual testing optimal for nonadaptive group testing? |
作者: | Huang, SH Hwang, FK 應用數學系 Department of Applied Mathematics |
關鍵字: | nonadaptive group testing;disjunct matrix;union-free matrix |
公開日期: | 2001 |
摘要: | The combinatorial group testing problem is, assuming the existence of up to d defectives among n items, to identify the defectives by as few tests as possible. In this paper, we study the problem for what values of n, given d, individual testing is optimal in nonadaptive group testing. Let N (d) denote the largest n for fixed d for which individual testing is optimal. We will show that N (d) = (d + 1)(2) under a prevalent constraint in practical nonadaptive algorithms and prove that N (d) = (d + 1)(2) for d = 1, 2, 3, 4 without any constraint. |
URI: | http://hdl.handle.net/11536/30040 http://dx.doi.org/10.1137/S0895480199359247 |
ISSN: | 0895-4801 |
DOI: | 10.1137/S0895480199359247 |
期刊: | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Volume: | 14 |
Issue: | 4 |
起始頁: | 540 |
結束頁: | 548 |
顯示於類別: | 期刊論文 |