Group Testing Algorithms: Bounds and Simulations
Group Testing Algorithms: Bounds and Simulations
复制标题
DOI：
10.1109/tit.2014.2314472
复制
发表时间：
2014-06-01
影响因子：
2.5
通讯作者：
Johnson, Oliver
中科院分区：
文献类型：
--
作者：
Aldridge, Matthew;Baldassini, Leonardo;Johnson, Oliver
研究了N个项目中K个项目有缺陷的非自适应无噪声群测试问题。我们描述了四种检测算法，Chan等人的COMP算法，两个新的算法，DD和SCOMP，这需要更强的证据来宣布一个项目有缺陷，和一个基本上是最佳的，但计算困难的算法称为SSS。我们考虑一类重要的设计组测试问题，即那些测试结构是通过伯努利随机过程。在这类Bernoulli设计中，通过考虑这些算法的渐近速度，我们证明了DD优于COMP，DD在K >= root N的情况下本质上是最优的，并且当K > N-0.35时，没有算法可以执行最好的非随机自适应算法。在模拟中，我们看到DD和SCOMP远远优于COMP，SCOMP非常接近最优SSS，特别是在K较大的情况下。
We consider the problem of nonadaptive noiseless group testing of N items of which K are defective. We describe four detection algorithms, the COMP algorithm of Chan et al., two new algorithms, DD and SCOMP, which require stronger evidence to declare an item defective, and an essentially optimal but computationally difficult algorithm called SSS. We consider an important class of designs for the group testing problem, namely those in which the test structure is given via a Bernoulli random process. In this class of Bernoulli designs, by considering the asymptotic rate of these algorithms, we show that DD outperforms COMP, that DD is essentially optimal in regimes where K >= root N, and that no algorithm can perform as well as the best nonrandom adaptive algorithms when K > N-0.35. In simulations, we see that DD and SCOMP far outperform COMP, with SCOMP very close to the optimal SSS, especially in cases with larger K.