A non-adaptive search algorithm that identifies up to three defects

We give a simple and constructable non-adaptive search algorithm that identifies a defective subset of cardinality at most three in a sample of cardinality n when the testing procedure can detect the presence of an odd number of defects in any subset of the sample. Our algorithm uses at most ⌈ log 2...

Full description

Saved in:
Bibliographic Details
Published in:Journal of statistical planning and inference 1997-05, Vol.60 (2), p.269-272
Main Author: Macula, Anthony J.
Format: Article
Language:English
Subjects:
Combinatorial search
Non-adaptive
Separating systems
Static
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We give a simple and constructable non-adaptive search algorithm that identifies a defective subset of cardinality at most three in a sample of cardinality n when the testing procedure can detect the presence of an odd number of defects in any subset of the sample. Our algorithm uses at most ⌈ log 2(n + 1) ⌉ + ( ⌈ log 2(n + 1) ⌉ 2 ) many tests.
ISSN:0378-3758
1873-1171
DOI:10.1016/S0378-3758(96)00144-9