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 条
  • [21] Group Testing Aggregate Signatures with Soundness
    Sato, Shingo
    Shikata, Junji
    Matsumoto, Tsutomu
    INFORMATION SECURITY AND CRYPTOLOGY - ICISC 2022, 2023, 13849 : 363 - 381
  • [22] Optimal group testing with heterogeneous risks
    Bobkova, Nina
    Chen, Ying
    Eraslan, Hulya
    ECONOMIC THEORY, 2024, 77 (1-2) : 413 - 444
  • [23] Adaptive Bayesian group testing: Algorithms and performance
    Bai, Yechao
    Wang, Qingsi
    Lo, Chun
    Liu, Mingyan
    Lynch, Jerome P.
    Zhang, Xinggan
    SIGNAL PROCESSING, 2019, 156 : 191 - 207
  • [24] Noisy group testing via spatial coupling
    Coja-Oghlan, Amin
    Hahn-Klimroth, Max
    Hintze, Lukas
    Kaaser, Dominik
    Krieg, Lena
    Rolvien, Maurice
    Scheftelowitsch, Olga
    COMBINATORICS PROBABILITY AND COMPUTING, 2024,
  • [25] Group Testing with a Graph Infection Spread Model
    Arasli, Batuhan
    Ulukus, Sennur
    INFORMATION, 2023, 14 (01)
  • [26] Noisy Adaptive Group Testing: Bounds and Algorithms
    Scarlett, Jonathan
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2019, 65 (06) : 3646 - 3661
  • [27] ABSI: An Adaptive Binary Splitting Algorithm for Malicious Meter Inspection in Smart Grid
    Xia, Xiaofang
    Xiao, Yang
    Liang, Wei
    IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, 2019, 14 (02) : 445 - 458
  • [28] Group testing in graphs
    Juan, Justie Su-Tzu
    Chang, Gerard J.
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2007, 14 (2-3) : 113 - 119
  • [29] Group Testing Game
    Bolouki, Sadegh
    Manshaei, Mohammad Hossein
    Ravanmehr, Vida
    Nedic, Angelia
    Basar, Tamer
    IFAC PAPERSONLINE, 2017, 50 (01): : 9668 - 9673
  • [30] Group Testing on a Network
    Silva, Arlei
    Singh, Ambuj
    THIRTY-FIFTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, THIRTY-THIRD CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE AND THE ELEVENTH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, 2021, 35 : 4348 - 4356