Non-Adaptive Randomized Algorithm for Group Testing
We study the problem of group testing with a non-adaptive randomized algorithm in the random incidence design (RID) model where each entry in the test is chosen randomly independently from $\{0,1\}$ with a fixed probability $p$. The property that is sufficient and necessary for a unique decoding is the separability of the tests, but unfortunately no linear time algorithm is known for such tests. In order to achieve linear-time decodable tests, the algorithms in the literature use the disjunction property that gives almost optimal number of tests. We define a new property for the tests which we call semi-disjunction property. We show that there is a linear time decoding for such test and for $d\to \infty$ the number of tests converges to the number of tests with the separability property and is therefore optimal (in the RID model). Our analysis shows that, in the RID model, the number of tests in our algorithm is better than the one with the disjunction property even for small $d$.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Concomitant Group Testing
In this paper, we introduce a variation of the group testing problem capturing the idea that a positive test requires a combination of multiple ``types'' of item. Specifically, we assume that there are multiple disjoint …
Bounds for the Number of Tests in Non-Adaptive Randomized Algorithms for Group Testing
We study the group testing problem with non-adaptive randomized algorithms. Several models have been discussed in the literature to determine how to randomly choose the tests. For a model ${\cal M}$, let $m_{\cal M}(n,d)…
On Detecting Some Defective Items in Group Testing
Group testing is an approach aimed at identifying up to $d$ defective items among a total of $n$ elements. This is accomplished by examining subsets to determine if at least one defective item is present. In our study, w…
Can machine learning solve the challenge of adaptive learning and the individualization of learning paths? A field experiment in an online learning platform
The individualization of learning contents based on digital technologies promises large individual and social benefits. However, it remains an open question how this individualization can be implemented. To tackle this q…
Self-LearningSparse Activity Discovery in Energy Constrained Multi-Cluster IoT Networks Using Group Testing
Current IoT networks are characterized by an ultra-high density of devices with different energy budget constraints, typically having sparse and sporadic activity patterns. Access points require an efficient strategy to …
Action DetectionActivity Detection