Conjectures on optimal nested generalized group testing algorithm

Yaakov Malinovsky

Applied Stochastic Models in Business and Industry, 2020, vol. 36, issue 6, 1029-1036

Abstract: Consider a finite population of N items, where item i has a probability pi 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 p1 = … = pN = 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 pi,i = 1,…,N belong to the R‐range, GPTA is the optimal procedure among nested procedures applied to pi of nondecreasing order; and (b) if all pi,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.

Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/asmb.2555

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:apsmbi:v:36:y:2020:i:6:p:1029-1036

Access Statistics for this article

More articles in Applied Stochastic Models in Business and Industry from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().