In group testing, the problem is to determine the defective members of a given set of elements O by performing tests on properly selected subsets of O. A response to a test is “yes” if the tested group contains one or more defective elements, and is “no” otherwise. The classical model of group testing has been recently generalized in a way such that the potentially contaminated sets are the hyperedges of a given hypergraph \(\mathcal{F}=(V,E)\) . This model takes into account how social and geographical clusterings affect the spreading of contaminations. The paper studies group testing algorithms with little adaptiveness, i.e., algorithms where tests are performed in stages and all tests performed in the same stage are decided at the beginning of the stage. In particular, the paper presents the first two-stage algorithm that uses \(o(d\log |E|)\) tests for arbitrary hypergraphs with hyperedges of size at most d, and a three-stage algorithm that improves by a \(d^{1/6}\) factor on the number of tests of the best so far known three-stage algorithm. These algorithms are special cases of an s-stage algorithm designed for an arbitrary positive integer \(s\le d\) . The design of this algorithm resorts to a new non-adaptive algorithm (one-stage algorithm), i.e., an algorithm where all tests must be decided beforehand. A major contribution of the paper consists in a non-existential result for non-adaptive group testing. Remarkably, this result implies the first lower bound for non-adaptive group testing that improves on the information theoretic lower bound \(\varOmega (\log |E|)\) and gets very close to the number of tests used by the best non-adaptive group testing algorithm.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Improved Bounds for Group Testing in Arbitrary Hypergraphs

  • Annalisa De Bonis

摘要

In group testing, the problem is to determine the defective members of a given set of elements O by performing tests on properly selected subsets of O. A response to a test is “yes” if the tested group contains one or more defective elements, and is “no” otherwise. The classical model of group testing has been recently generalized in a way such that the potentially contaminated sets are the hyperedges of a given hypergraph \(\mathcal{F}=(V,E)\) . This model takes into account how social and geographical clusterings affect the spreading of contaminations. The paper studies group testing algorithms with little adaptiveness, i.e., algorithms where tests are performed in stages and all tests performed in the same stage are decided at the beginning of the stage. In particular, the paper presents the first two-stage algorithm that uses \(o(d\log |E|)\) tests for arbitrary hypergraphs with hyperedges of size at most d, and a three-stage algorithm that improves by a \(d^{1/6}\) factor on the number of tests of the best so far known three-stage algorithm. These algorithms are special cases of an s-stage algorithm designed for an arbitrary positive integer \(s\le d\) . The design of this algorithm resorts to a new non-adaptive algorithm (one-stage algorithm), i.e., an algorithm where all tests must be decided beforehand. A major contribution of the paper consists in a non-existential result for non-adaptive group testing. Remarkably, this result implies the first lower bound for non-adaptive group testing that improves on the information theoretic lower bound \(\varOmega (\log |E|)\) and gets very close to the number of tests used by the best non-adaptive group testing algorithm.