...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Optimal Algorithms for Two Group Testing Problems, and New Bounds on Generalized Superimposed Codes
【24h】

Optimal Algorithms for Two Group Testing Problems, and New Bounds on Generalized Superimposed Codes

机译：两组测试问题的最佳算法以及广义叠加码的新界

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Two variants of the well-known group testing problem are considered. In the first variant a finite set of items$O$and an unknown subset$Psubseteq O$are given, and one wants to identify the set$P$by asking the least number of questions of the form “Is$vert Qcap Pvert =1$?”, where$Qsubseteq O$. This problem naturally arises in the design of efficient contention resolution algorithms for certain random multiple-access communication systems [Berger et al. “Random multiple-access communication and group testing,” IEEE Trans. Commun., vol. 32, no. 7, pp. 769–779, 1984]. In the second variant of the problem, the answer to the question “Is$vert Qcap Pvert =1$?” is correctly YES if$vert Qcap Pvert =1$and NO if$vert Qcap Pvert =0$”, and it is left to a (possibly malicious) adversary otherwise. This model was introduced in [Damaschke, “Randomized group testing for mutually obscuring defectives,” Inf. Process. Lett., vol. 67, pp. 131–135, 1998], in the context of chemical compound testing. In this correspondence several algorithms for these group testing problems are presented, trying to optimize different measures of performance: The overall number of tests performed by the algorithm, the number of stages in which tests can be arranged, and the decoding complexity of identifying the elements of$P$from tests outcomes. Some of the given algorithms are optimal with respect to more than one of the above criteria. Instrumental to the results presented in the correspondence are new and improved bounds on certain generalization of superimposed codes introduced in [Dyachkov and Rykov, “A generalization of superimposed codes and its application to the multiple-access channel,” in Proc. 1984 IEEE Int. Symp. Inf. Theory, pp. 62–64], [De Bonis and Vaccaro, “Constructions of generalized superimposed codes with applications to group testing and conflict resolution in multiple access channels,” Theoretic. Comput. Sci., vol. 306, no. 1–3,- pp. 223–243, 2003] a result that it is believed to be of independent interest.
机译：考虑了众所周知的组测试问题的两个变体。在第一个变体中，给出了一组有限的项目$ O $和一个未知的子集$ Psubseteq O $，一个人想通过询问最少数量的“ Is $ vert Qcap Pvert = 1 $？”，其中$ Qsubseteq O $。在某些随机多址通信系统的有效争用解决算法的设计中，自然会出现这个问题[Berger等人。 “随机多址通信和组测试”，IEEE Trans。社区卷。 32号7，第769–779页，1984年]。在问题的第二个变体中，问题的答案是“ $ vert Qcap Pvert = 1 $吗？”如果$ vert Qcap Pvert = 1 $是正确的，如果$ vert Qcap Pvert = 0 $是正确的，否则将其留给（可能是恶意的）对手。该模型在[Damaschke，“互斥缺陷的随机分组测试”，Inf。处理。 Lett。，第一卷67，第131–135页，1998年]，在化合物测试中。在此对应关系中，提出了针对这些组测试问题的几种算法，以尝试优化性能的不同度量：该算法执行的测试总数，可以安排测试的阶段数以及识别元素的解码复杂性测试结果中的$ P $。相对于以上标准之一，某些给定算法是最佳的。对对应关系中呈现的结果有帮助的是[Dyachkov和Rykov，Proc.Natl.Av。 1984 IEEE国际症状Inf。理论，第62–64页，[De Bonis和Vaccaro，“广义叠加代码的构造及其在多访问通道中的组测试和冲突解决的应用”，理论。计算科学，卷。 306号[2003年第1-3页，第223-243页]的结果被认为具有独立利益。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号