Nonadaptive group testing with lies: Probabilistic existence theorems

Zhigljavsky, Anatoly Alexandrovich ORCID: https://orcid.org/0000-0003-0630-8279 2010. Nonadaptive group testing with lies: Probabilistic existence theorems. Journal of Statistical Planning and Inference 140 (10) , pp. 2825-2893. 10.1016/j.jspi.2010.03.012

Preview

Text Download (186kB) | Preview

Abstract

We consider a wide range of combinatorial group testing problems with lies including binary, additive and multiaccess channel group testing problems. We derive upper bounds for the number of tests in the optimal nonadaptive algorithms. The derivation is probabilistic and is therefore non-constructive; it does not provide the way of constructing optimal algorithms. In the asymptotic setting, we show that the leading term for the number of tests does not depend on the number of lies and it is thus the same as for the zero-lie case. However, the other terms in the asymptotic upper bounds depend on the number of lies and substantially influence the upper bounds in the non-asymptotic situation.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics
Uncontrolled Keywords:	Probabilistic method; Existence theorems; Group testing; Significant factors; Multiaccess channel; Searching with lies
Publisher:	Elsevier
ISSN:	0378-3758
Last Modified:	11 May 2023 11:51
URI:	https://orca.cardiff.ac.uk/id/eprint/15201

Citation Data

Cited 1 time in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item