A nonadaptive version of Ulam's problem with one lie (Q1360979)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A nonadaptive version of Ulam's problem with one lie |
scientific article; zbMATH DE number 1038352
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A nonadaptive version of Ulam's problem with one lie |
scientific article; zbMATH DE number 1038352 |
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
