Subquadratic non-adaptive threshold group testing

被引：0

作者：

De Marco, Gianluca ^{[1
]}

Jurdzinski, Tomasz ^{[2
]}

Kowalski, Dariusz R. ^{[3
,4
]}

Rozanski, Michal ^{[4
]}

Stachowiak, Grzegorz ^{[2
]}

机构：

[1] Univ Salerno, Dipartimento Informat, Fisciano, Italy

[2] Univ Wroclaw, Inst Comp Sci, Wroclaw, Poland

[3] Augusta Univ, Sch Comp & Cyber Sci, Augusta, GA USA

[4] SWPS Univ Social Sci & Humanities, Warsaw, Poland

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2020年 / 111卷

关键词：

Group testing; Threshold group testing; Non-adaptive strategies; Probabilistic method; Deterministic algorithms; DISTRIBUTED BROADCAST; ALGORITHMS; RESOLUTION; CHANNELS;

D O I：

10.1016/j.jcss.2020.02.002

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We consider threshold group testing - a generalization of group testing, which asks to identify a set of positive individuals in a population, by performing tests on pools of elements. Each test is represented by a subset Q of individuals and its output is yes if Q contains at least one positive element and no otherwise. Threshold group testing is the natural generalization, introduced by P. Damaschke in 2005, arising when we are given a threshold t>0 and the answer to a test Q is yes if Q contains at least t positives and no otherwise. We give upper and lower bounds for this general problem, showing a complexity separation with the classical group testing. Next, we introduce a further generalization in which the goal is minimizing not only the number of tests, but also the number of thresholds which is related to the accuracy of the tests. (C) 2020 Elsevier Inc. All rights reserved.

引用

页码：42 / 56

页数：15

共 39 条

[1] Optimal Monotone Encodings [J].