论文标题
改进了阈值组测试的非自适应算法
Improved non-adaptive algorithms for threshold group testing with a gap
论文作者
论文摘要
阈值组测试的基本目标是确定$ n $项目中最多$ d $有缺陷的物品，其中$ d $通常比$ n $小得多。如果子集至少具有$ u $有缺陷的项目，则对项目子集的测试结果为正，如果它具有$ \ ell $有缺陷的项目，则为$ 0 \ leq \ ell <u $，否则是任意的。这称为阈值组测试。参数$ g = u- \ ell-1 $称为\ textit {gap}。在本文中，我们专注于$ g> 0 $，即有间隙的阈值组测试。请注意，此处提供的结果也适用于$ g = 0 $的情况。但是，结果不如相关工作的结果效率。目前，一些报告的研究研究了测试设计和解码算法，以识别有缺陷的项目。以前的大多数研究都不可行，因为他们的问题设置有许多限制，或者其提议方案的解码复杂性相对较大。因此，强制性减少测试的数量以及解码的复杂性，即确定有缺陷项目的时间，以实现实际方案。 这里介绍的工作做出了五项贡献。第一个是针对Chen和Fu提出的阈值组测试的非自适应算法的更准确定理。第二个是对分离矩阵的构建的改进，这是解决（阈值）组测试的主要工具以及其他任务，例如构建封面的家庭或学习隐藏的图形。第三和第四贡献是在测试数量上的确切上限减少，并且在解码时间上降低了渐近线，以在测试结果上噪声设置中识别有缺陷的项目。第五个贡献是对先前工作和提议定理的结果改进的测试数量的模拟。
The basic goal of threshold group testing is to identify up to $d$ defective items among a population of $n$ items, where $d$ is usually much smaller than $n$. The outcome of a test on a subset of items is positive if the subset has at least $u$ defective items, negative if it has up to $\ell$ defective items, where $0\leq\ell<u$, and arbitrary otherwise. This is called threshold group testing. The parameter $g=u-\ell-1$ is called \textit{the gap}. In this paper, we focus on the case $g>0$, i.e., threshold group testing with a gap. Note that the results presented here are also applicable to the case $g = 0$; however, the results are not as efficient as those in related work. Currently, a few reported studies have investigated test designs and decoding algorithms for identifying defective items. Most of the previous studies have not been feasible because there are numerous constraints on their problem settings or the decoding complexities of their proposed schemes are relatively large. Therefore, it is compulsory to reduce the number of tests as well as the decoding complexity, i.e., the time for identifying the defective items, for achieving practical schemes. The work presented here makes five contributions. The first is a more accurate theorem for a non-adaptive algorithm for threshold group testing proposed by Chen and Fu. The second is an improvement in the construction of disjunct matrices, which are the main tools for tackling (threshold) group testing and other tasks such as constructing cover-free families or learning hidden graphs. The third and fourth contributions are a reduced exact upper bound on the number of tests and a reduced asymptotic bound on the decoding time for identifying defective items in a noisy setting on test outcomes. The fifth contribution is a simulation on the number of tests of the resulting improvements for previous work and the proposed theorems.
