A nonadaptive version of Ulam's problem with one lie
type: Item
instance of: scholarly article
title: A nonadaptive version of Ulam's problem with one lie
zbMATH Open document ID: 0889.05031
DOI: 10.1016/S0378-3758(96)00145-0
author: Anthony J. Macula
published in: Journal of Statistical Planning and Inference
publication date: 1998-06-02T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 62K99
Mathematics Subject Classification ID: 94A15
Mathematics Subject Classification ID: 94B99
zbMATH DE Number: 1038352
zbMATH Keywords: group testing
zbMATH Keywords: Ulam's problem
reviewed by: Du Ding-Zhu
MaRDI profile type: Publication
cites work: Q3994535
cites work: Ulam's searching game with lies
cites work: Q4857782
cites work: On separating systems of a finite set
cites work: Q4035998
cites work: Q4304384
cites work: Coding Theory Applied to a Problem of Ulam
cites work: On separating systems whose elements are sets of at most k elements
full work available at URL: s0378-3758(96)00145-0
OpenAlex ID: W2072412961
description: scientific article; zbMATH DE number 1038352