Strongly separable matrices for nonadaptive combinatorial group testing
Strongly separable matrices for nonadaptive combinatorial group testing
复制标题
DOI：
10.1016/j.dam.2020.11.022
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Jinping Fan;H. Fu;Yujie Gu;Y. Miao;Maiko Shigeno
中科院分区：
文献类型：
--
作者：
Jinping Fan;H. Fu;Yujie Gu;Y. Miao;Maiko Shigeno
在非自适应组合成组测试(CGT)中，人们希望用尽可能少的测试(即大率)和有效的识别算法从n个项目的大样本中识别出最多d个缺陷的小集合。在文献中，d-析取矩阵(d-DM)和d-̄-可分矩阵(d-̄-SM)是研究了几十年的两种经典组合结构。众所周知，d-DM提供了比d-̄-SM更有效的识别算法，而d-̄-SM可能具有比d-DM更大的速率。为了结合这两种结构的优点，本文提出了一种强d-可分矩阵的新概念，它介于d-DM和d-̄-SM之间。我们证明了d-̄-SM具有比d-SSM更有效的识别算法，并且最大速率不小于d-DM。此外，还建立了d-SSM最大速率的一般界。此外，通过带删除的随机编码方法，我们得到了2-SSM的最大码率的一个改进的下界，它比2-DM的最好结果高得多。
In nonadaptive combinatorial group testing (CGT), it is desirable to identify a small set of up to d defectives from a large population of n items with as few tests (ie large rate) and efficient identifying algorithm as possible. In the literature, d-disjunct matrices (d-DM) and d ̄-separable matrices (d ̄-SM) are two classical combinatorial structures having been studied for several decades. It is well-known that a d-DM provides a more efficient identifying algorithm than a d ̄-SM, while a d ̄-SM could have a larger rate than a d-DM. In order to combine the advantages of these two structures, in this paper, we introduce a new notion of strongly d-separable matrix (d-SSM) for nonadaptive CGT, which is sandwiched between d-DM and d ̄-SM. We show that a d-SSM has the identifying algorithm more efficient than a d ̄-SM, as well as the largest rate no less than a d-DM. In addition, the general bounds on the largest rate of d-SSM are established. Moreover, by the random coding method with expurgation, we derive an improved lower bound on the largest rate of 2-SSM which is much higher than the best known result of 2-DM.