A nonadaptive version of Ulam's problem with one lie (Q1360979)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A nonadaptive version of Ulam's problem with one lie |
scientific article |
Statements
A nonadaptive version of Ulam's problem with one lie (English)
0 references
2 June 1998
0 references
Given \(n\) items with one defective, identify the defective with the minimum number of tests each of which tells whether a subset of items contains the defective. This is a group testing problem. Moreover, if at most \(r\) tests are allowed to lie, then the problem is called Ulam's problem with \(r\) lies. In the literature, the minimum number of tests has been determined for Ulam's problem with \(r\) lies for \(r\leq 2\). In this paper, the author considers a nonadaptive version of Ulam's problem with one lie. Lower and upper bounds for the minimum number of tests are obtained.
0 references
group testing
0 references
Ulam's problem
0 references
