Quaternary splitting algorithm in group testing

被引:0
作者
Lu, Jinn [1 ]
Fu, Hung-Lin [1 ]
机构
[1] Natl Chiao Tung Univ, Dept Appl Math, Hsinchu 30010, Taiwan
关键词
Group testing; Adaptive algorithm; Quaternary splitting; DEFECTIVE MEMBERS;
D O I
10.1007/s10878-020-00661-6
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
In Classical group testing, one is given a population of n items N which contains some defective d items inside. A group test (pool) is a test on a subset of N. Under the circumstance of no errors, a test is negative if the testing pool contains no defective items and the test is positive if the testing pool contains at least one defective item but we don't know which one. The goal is to find all defectives by using as less tests as possible, mainly to minimize the number of tests (in the worst case situation). Let M(d, n) denote the minimum number of tests in the worst case situation where vertical bar N vertical bar = n and d is the number of defectives. In this paper, we focus on estimating M(d, n) and obtain a better result than known ones in various cases of d and n.
引用
收藏
页码:73 / 79
页数:7
相关论文
共 50 条
  • [31] Blind Group Testing
    Huleihel, Wasim
    Elishco, Ohad
    Medard, Muriel
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2019, 65 (08) : 5050 - 5063
  • [32] Optimal group testing
    Coja-Oghlan, Amin
    Gebhard, Oliver
    Hahn-Klimroth, Max
    Loick, Philipp
    COMBINATORICS PROBABILITY AND COMPUTING, 2021, 30 (06) : 811 - 848
  • [33] Group testing in graphs
    Justie Su-tzu Juan
    Gerard J. Chang
    Journal of Combinatorial Optimization, 2007, 14 : 113 - 119
  • [34] Generalized Group Testing
    Cheng, Xiwei
    Jaggi, Sidharth
    Zhou, Qiaoqiao
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2023, 69 (03) : 1413 - 1451
  • [35] A Zig-Zag Approach for Competitive Group Testing
    Cheng, Yongxi
    Du, Ding-Zhu
    Xu, Yinfeng
    INFORMS JOURNAL ON COMPUTING, 2014, 26 (04) : 677 - 689
  • [36] An improved zig zag approach for competitive group testing
    Wu, Jun
    Cheng, Yongxi
    Du, Ding-Zhu
    DISCRETE OPTIMIZATION, 2022, 43
  • [37] Semiquantitative Group Testing
    Emad, Amin
    Milenkovic, Olgica
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2014, 60 (08) : 4614 - 4636
  • [38] Dynamic Infection Spread Model Based Group Testing
    Arasli, Batuhan
    Ulukus, Sennur
    ALGORITHMS, 2023, 16 (01)
  • [39] Modelling the utility of group testing for public health surveillance
    Koliander, Gunther
    Pichler, Georg
    INFECTIOUS DISEASE MODELLING, 2021, 6 : 1009 - 1024
  • [40] Group Testing under Sum Observations for Heavy Hitter Detection
    Wang, Chao
    Zhao, Qing
    Chuah, Chen-Nee
    2015 INFORMATION THEORY AND APPLICATIONS WORKSHOP (ITA), 2015, : 149 - 153