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 条
  • [1] Quaternary splitting algorithm in group testing
    Jinn Lu
    Hung-Lin Fu
    Journal of Combinatorial Optimization, 2021, 41 : 73 - 79
  • [2] Fast splitting algorithms for sparsity-constrained and noisy group testing
    Price, Eric
    Scarlett, Jonathan
    Tan, Nelvin
    INFORMATION AND INFERENCE-A JOURNAL OF THE IMA, 2023, 12 (02) : 1141 - 1171
  • [3] On the optimal configuration of a square array group testing algorithm
    Cizikoviene, Ugne
    Skorniakov, Viktor
    STATISTICS AND ITS INTERFACE, 2023, 16 (01) : 579 - 591
  • [4] A new strongly competitive group testing algorithm with small sequentiality
    Cheng, Yongxi
    Du, Ding-Zhu
    Zheng, Feifeng
    ANNALS OF OPERATIONS RESEARCH, 2015, 229 (01) : 265 - 286
  • [5] On the optimal pairwise group testing algorithm
    Cizikoviene, Ugne
    Skorniakov, Viktor
    BRAZILIAN JOURNAL OF PROBABILITY AND STATISTICS, 2024, 38 (02) : 253 - 265
  • [6] An efficient algorithm for group testing with runlength constraints
    Dalai, Marco
    Della Fiore, Stefano
    Rescigno, Adele A.
    Vaccaro, Ugo
    DISCRETE APPLIED MATHEMATICS, 2025, 360 : 181 - 187
  • [7] A group testing algorithm with online informational learning
    Kagan, Eugene
    Ben-Gal, Irad
    IIE TRANSACTIONS, 2014, 46 (02) : 164 - 184
  • [8] Conjectures on optimal nested generalized group testing algorithm
    Malinovsky, Yaakov
    APPLIED STOCHASTIC MODELS IN BUSINESS AND INDUSTRY, 2020, 36 (06) : 1029 - 1036
  • [9] Tropical Group Testing
    Wang, Hsin-Po
    Gabrys, Ryan
    Vardy, Alexander
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2023, 69 (09) : 6098 - 6120
  • [10] Concomitant Group Testing
    Bui, Thach V.
    Scarlett, Jonathan
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2024, 70 (10) : 7179 - 7192