首页> 外文期刊>Algorithmica >Improved Constructions for Non-adaptive Threshold Group Testing
【24h】

Improved Constructions for Non-adaptive Threshold Group Testing

机译:非自适应阈值组测试的改进构造

获取原文
获取原文并翻译 | 示例

摘要

The basic goal in combinatorial group testing is to identify a set of up to d defective items within a large population of size n » d using a pooling strategy. Namely, the items can be grouped together in pools, and a single measurement would reveal whether there are one or more defectives in the pool. The threshold model is a generalization of this idea where a measurement returns positive if the number of defectives in the pool reaches a fixed threshold u > 0, negative if this number is no more than a fixed lower threshold ℓ < u, and may behave arbitrarily otherwise. We study non-adaptive threshold group testing (in a possibly noisy setting) and show that, for this problem, O(d~(g+2)(log d) log(n/d)) measurements (where g := u - ℓ - 1 and u is any fixed constant) suffice to identify the defectives, and also present almost matching lower bounds. This significantly improves the previously known (non-constructive) upper bound O(d~(u+1) log(n/d)). Moreover, we obtain a framework for explicit construction of measurement schemes using lossless condensers. The number of measurements resulting from this scheme is ideally bounded by O(d~(g+3)(logd) log n). Using state-of-the-art constructions of lossless condensers, however, we obtain explicit testing schemes with O(d~(g+3)(logd)quasipoly(logn)) and O(d~(g+3+β)poly(logn)) measurements, for arbitrary constant β > 0.
机译:组合组测试的基本目标是使用合并策略在大小为n»d的总体中识别出多达d个有缺陷的项目。即,可以将这些项目分组到一个池中,并且一次测量即可显示该池中是否存在一个或多个缺陷。阈值模型是该思想的概括,其中,如果池中的缺陷数量达到固定阈值u> 0,则度量返回正数;如果该数量不超过固定的下阈值ℓ 0。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号