Strongly separable matrices for nonadaptive combinatorial group testing
In: Discrete Applied Mathematics, Jg. 291 (2021-03-01), S. 180-187
Online
unknown
Zugriff:
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 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.
Titel: |
Strongly separable matrices for nonadaptive combinatorial group testing
|
---|---|
Autor/in / Beteiligte Person: | Shigeno, Maiko ; Fan, Jinping ; Miao, Ying ; Fu, Hung-Lin ; Gu, Yujie |
Link: | |
Zeitschrift: | Discrete Applied Mathematics, Jg. 291 (2021-03-01), S. 180-187 |
Veröffentlichung: | Elsevier BV, 2021 |
Medientyp: | unknown |
ISSN: | 0166-218X (print) |
DOI: | 10.1016/j.dam.2020.11.022 |
Schlagwort: |
|
Sonstiges: |
|