Conjectures on optimal nested generalized group testing algorithm. (22nd July 2020)

• Record Type: Journal Article
• Authors: Malinovsky, Yaakov
• Other Names: Baron Michael guestEditor.; Yashchin Emmanuel guestEditor.
• Is Part Of: Applied stochastic models in business and industry. Volume 36:Number 6(2020)
• Page Start: 1029
• Page End: 1036
• Publication Date: 2020-07-22
• Subjects: individual testing -- pairwise testing; Stochastic analysis -- Periodicals; Stochastic processes -- Periodicals; Business mathematics -- Periodicals; Finance -- Mathematical models -- Periodicals; Industrial management -- Mathematical models -- Periodicals; 338.00151923
• DOI: 10.1002/asmb.2555
• Languages: English
• ISSNs: 1524-1904

Abstract

Abstract: Consider a finite population of N items, where item i has a probability p i to be defective. The goal is to identify all items by means of group testing. This is the generalized group testing problem (hereafter GGTP). In the case of p 1 = … = p N = p, Yao and Hwang (1990) proved that the pairwise testing algorithm is the optimal nested algorithm, with respect to the expected number of tests, for all N if and only if p ∈ [ 1 − 1 / 2, ( 3 − 5 ) / 2 ] (R‐range hereafter) (an optimal at the boundary values). In this note, we present a result that helps to define the generalized pairwise testing algorithm (hereafter GPTA) for the GGTP. We present two conjectures: (a) when all p i, i = 1, …, N belong to the R‐range, GPTA is the optimal procedure among nested procedures applied to p i of nondecreasing order; and (b) if all p i, i = 1, …, N belong to the R‐range, GPTA is the optimal nested procedure, that is, minimizes the expected total number of tests with respect to all possible testing orders in the class of nested procedures. Although these conjectures are logically reasonable, we were only able to empirically verify the first one up to a particular level of N . We also provide a short survey of GGTP.