Finding a Burst of Positives via Nonadaptive Semiquantitative Group Testing
share
Motivated by testing for pathogenic diseases we consider a new nonadaptive group testing problem for which: (1) positives occur within a burst, capturing the fact that infected test subjects often come in clusters, and (2) that the test outcomes arise from semiquantitative measurements that provide coarse information about the number of positives in any tested group. Our model generalizes prior work on detecting a single burst of positives with classical group testing[1] as well as work on semiquantitative group testing (SQGT)[2]. Specifically, we study the setting where the burst-length ℓ is known and the semiquantitative tests provide potentially nonuniform estimates on the number of positives in a test group. The estimates represent the index of a quantization bin containing the (exact) total number of positives, for arbitrary thresholds η_1,…,η_s. Interestingly, we show that the minimum number of tests needed for burst identification is essentially only a function of the largest threshold η_s. In this context, our main result is an order-optimal test scheme that can recover any burst of length ℓ using roughly ℓ/2η_s+log_s+1(n) measurements. This suggests that a large saturation level η_s is more important than finely quantized information when dealing with bursts. We also provide results for related modeling assumptions and specialized choices of thresholds.
READ FULL TEXT