On the optimality of some group testing algorithms

Matthew Aldridge

doi:10.1109/ISIT.2017.8007097

On the optimality of some group testing algorithms

Matthew Aldridge

Department of Mathematical Sciences

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

9 Citations (SciVal)

88 Downloads (Pure)

Abstract

We consider Bernoulli nonadaptive group testing with k=Θ(n^θ) defectives, for θ∈(0,1). The practical definite defectives (DD) detection algorithm is known to be optimal for θ≥1/2. We give a new upper bound on the rate of DD, showing that DD is strictly suboptimal for θ<0.41. We also show that the SCOMP algorithm and algorithms based on linear programming achieve a rate at least as high as DD, so in particular are also optimal for θ≥1/2.

Original language	English
Title of host publication	Proceedings of 2017 IEEE International Symposium on Information Theory (ISIT)
Publisher	IEEE
Pages	3085-3089
ISBN (Electronic)	2157-8117
DOIs	https://doi.org/10.1109/ISIT.2017.8007097
Publication status	Published - Jun 2017
Event	2017 IEEE International Symposium on Information Theory (ISIT) - Aachen, Germany Duration: 25 Jun 2017 → 30 Jun 2017

Conference

Conference	2017 IEEE International Symposium on Information Theory (ISIT)
Period	25/06/17 → 30/06/17

Access to Document

10.1109/ISIT.2017.8007097

optimality-group-testing (5)
(c) 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works. The final published version is available via http://doi.org/10.1109/ISIT.2017.8007097
Accepted author manuscript, 366 KB

Cite this

@inproceedings{b15ed6bf5cd740b7a2feff52815e8b3a,

title = "On the optimality of some group testing algorithms",

abstract = "We consider Bernoulli nonadaptive group testing with k=Θ(n\textasciicircum{}θ) defectives, for θ∈(0,1). The practical definite defectives (DD) detection algorithm is known to be optimal for θ≥1/2. We give a new upper bound on the rate of DD, showing that DD is strictly suboptimal for θ<0.41. We also show that the SCOMP algorithm and algorithms based on linear programming achieve a rate at least as high as DD, so in particular are also optimal for θ≥1/2.",

author = "Matthew Aldridge",

year = "2017",

month = jun,

doi = "10.1109/ISIT.2017.8007097",

language = "English",

pages = "3085--3089",

booktitle = "Proceedings of 2017 IEEE International Symposium on Information Theory (ISIT)",

publisher = "IEEE",

address = "USA United States",

note = "2017 IEEE International Symposium on Information Theory (ISIT) ; Conference date: 25-06-2017 Through 30-06-2017",

}

TY - GEN

T1 - On the optimality of some group testing algorithms

AU - Aldridge, Matthew

PY - 2017/6

Y1 - 2017/6

N2 - We consider Bernoulli nonadaptive group testing with k=Θ(n^θ) defectives, for θ∈(0,1). The practical definite defectives (DD) detection algorithm is known to be optimal for θ≥1/2. We give a new upper bound on the rate of DD, showing that DD is strictly suboptimal for θ<0.41. We also show that the SCOMP algorithm and algorithms based on linear programming achieve a rate at least as high as DD, so in particular are also optimal for θ≥1/2.

AB - We consider Bernoulli nonadaptive group testing with k=Θ(n^θ) defectives, for θ∈(0,1). The practical definite defectives (DD) detection algorithm is known to be optimal for θ≥1/2. We give a new upper bound on the rate of DD, showing that DD is strictly suboptimal for θ<0.41. We also show that the SCOMP algorithm and algorithms based on linear programming achieve a rate at least as high as DD, so in particular are also optimal for θ≥1/2.

U2 - 10.1109/ISIT.2017.8007097

DO - 10.1109/ISIT.2017.8007097

M3 - Chapter in a published conference proceeding

SP - 3085

EP - 3089

BT - Proceedings of 2017 IEEE International Symposium on Information Theory (ISIT)

PB - IEEE

T2 - 2017 IEEE International Symposium on Information Theory (ISIT)

Y2 - 25 June 2017 through 30 June 2017

ER -

On the optimality of some group testing algorithms

Abstract

Conference

Access to Document

Fingerprint

Cite this