TY - GEN

T1 - A New Algorithm for Two-Stage Group Testing

AU - Vorobyev, Ilya

PY - 2019/7

Y1 - 2019/7

N2 - Group testing is a well-known search problem that consists in detecting of s defective members of a set of t samples by carrying out tests on properly chosen subsets of samples. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests in the worst case. In this work, two-stage group testing is considered. Using the hypergraph approach we design a new search algorithm, which allows improving the known results for fixed s and t→ ∞. For the case s = 2 this algorithm achieves information-theoretic lower bound 2 log2 t(1+o(1)) on the number of tests in the worst case. Also, the problem of finding m out of s defectives is considered.

AB - Group testing is a well-known search problem that consists in detecting of s defective members of a set of t samples by carrying out tests on properly chosen subsets of samples. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests in the worst case. In this work, two-stage group testing is considered. Using the hypergraph approach we design a new search algorithm, which allows improving the known results for fixed s and t→ ∞. For the case s = 2 this algorithm achieves information-theoretic lower bound 2 log2 t(1+o(1)) on the number of tests in the worst case. Also, the problem of finding m out of s defectives is considered.

UR - http://www.scopus.com/inward/record.url?scp=85073158089&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2019.8849718

DO - 10.1109/ISIT.2019.8849718

M3 - Conference contribution

AN - SCOPUS:85073158089

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 101

EP - 105

BT - 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2019 IEEE International Symposium on Information Theory, ISIT 2019

Y2 - 7 July 2019 through 12 July 2019

ER -