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 条
  • [41] Strong Converses for Group Testing From Finite Blocklength Results
    Johnson, Oliver
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2017, 63 (09) : 5923 - 5933
  • [42] Noisy Adaptive Group Testing via Noisy Binary Search
    Teo, Bernard
    Scarlett, Jonathan
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2022, 68 (05) : 3340 - 3353
  • [43] Optimal Multi-broadcast with Beeps Using Group Testing
    Beauquier, Joffroy
    Burman, Janna
    Davies, Peter
    Dufoulon, Fabien
    STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY, SIROCCO 2019, 2019, 11639 : 66 - 80
  • [44] Group testing: Revisiting the ideas
    Skorniakov, Viktor
    Leipus, Remigijus
    Juzeliunas, Gediminas
    Staliunas, Kestutis
    NONLINEAR ANALYSIS-MODELLING AND CONTROL, 2021, 26 (03): : 534 - 549
  • [45] Nested Group Testing Procedure
    Xiong, Wenjun
    Ding, Juan
    Zhang, Wei
    Liu, Aiyi
    Li, Qizhai
    COMMUNICATIONS IN MATHEMATICS AND STATISTICS, 2023, 11 (04) : 663 - 693
  • [46] The Capacity of Adaptive Group Testing
    Baldassini, Leonardo
    Johnson, Oliver
    Aldridge, Matthew
    2013 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY PROCEEDINGS (ISIT), 2013, : 2676 - +
  • [47] Note on a conjecture for group testing
    Leu, MG
    Lin, CY
    Weng, SY
    ARS COMBINATORIA, 2002, 64 : 29 - 32
  • [48] Group testing for connected communities
    Nikolopoulos, Pavlos
    Srinivasavaradhan, Sundara Rajan
    Guo, Tao
    Fragouli, Christina
    Diggavi, Suhas
    24TH INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND STATISTICS (AISTATS), 2021, 130
  • [49] Group testing for image compression
    Hong, ES
    Ladner, RE
    IEEE TRANSACTIONS ON IMAGE PROCESSING, 2002, 11 (08) : 901 - 911
  • [50] Sparse Combinatorial Group Testing
    Inan, Huseyin A.
    Kairouz, Peter
    Ozgur, Ayfer
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2020, 66 (05) : 2729 - 2742