论文标题
非适应性组合群测试的强大可分离矩阵
Strongly separable matrices for nonadaptive combinatorial group testing
论文作者
论文摘要
在非适应性组合组测试（CGT）中，希望从大量的$ n $项目中识别出一小部分$ d $ debectives，其中少量测试（即大比率）和有效的识别算法。在文献中，$ d $ disjunct矩阵（$ d $ -dm）和$ \ bar {d} $ - 可分开的矩阵（$ \ bar {d} $ - sm）是两种经典的组合结构已经研究了几十年。众所周知，与$ \ bar {d} $ - SM相比，A $ D $ -DM提供了更有效的识别算法，而$ \ bar {d} $ - SM的速率可能比$ d $ dm的速率更高。为了结合这两种结构的优势，在本文中，我们引入了一个新的概念\ emph {强烈$ d $ - 可分离的矩阵}（$ d $ -ssmsm）（$ d $ -ssm），并表明$ d $ -SSM具有与$ d $ -d $ d $ dm $ $ deber的识别能力相同，但比$ d $ d $ dmer-d $ dm-d $ dm-d $ dm-dm-dem-dem-d $ dm-dm-dm-dm-dm-dm-dm-ddm-ddm-ddm-ddm-ddm-ddm-ddm-ddm--ddm-ddm。因此，建立了$ 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 (i.e. large rate) and efficient identifying algorithm as possible. In the literature, $d$-disjunct matrices ($d$-DM) and $\bar{d}$-separable matrices ($\bar{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 $\bar{d}$-SM, while a $\bar{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 \emph{strongly $d$-separable matrix} ($d$-SSM) for nonadaptive CGT and show that a $d$-SSM has the same identifying ability as a $d$-DM, but much weaker requirements than a $d$-DM. Accordingly, the general bounds on the largest rate of a $d$-SSM are established. Moreover, by the random coding method with expurgation, we derive an improved lower bound on the largest rate of a $2$-SSM which is much higher than the best known result of a $2$-DM.
