On the Cut-off Point for Combinatorial Group Testing

Publication: Research - peer-reviewJournal article – Annual report year: 1999

Standard

On the Cut-off Point for Combinatorial Group Testing. / Fischer, Paul; Klasner, N.; Wegener, I.

In: Discrete Applied Mathematics, Vol. 91, No. 1-3, 1999, p. 83-92.

Publication: Research - peer-reviewJournal article – Annual report year: 1999

Harvard

Fischer, P, Klasner, N & Wegener, I 1999, 'On the Cut-off Point for Combinatorial Group Testing' Discrete Applied Mathematics, vol 91, no. 1-3, pp. 83-92.

APA

CBE

MLA

Vancouver

Author

Fischer, Paul; Klasner, N.; Wegener, I. / On the Cut-off Point for Combinatorial Group Testing.

In: Discrete Applied Mathematics, Vol. 91, No. 1-3, 1999, p. 83-92.

Publication: Research - peer-reviewJournal article – Annual report year: 1999

Bibtex

@article{157168338b2846b2b12ecd0ae74d34a7,
title = "On the Cut-off Point for Combinatorial Group Testing",
publisher = "Elsevier BV North-Holland",
author = "Paul Fischer and N. Klasner and I. Wegener",
year = "1999",
volume = "91",
number = "1-3",
pages = "83--92",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",

}

RIS

TY - JOUR

T1 - On the Cut-off Point for Combinatorial Group Testing

A1 - Fischer,Paul

A1 - Klasner,N.

A1 - Wegener,I.

AU - Fischer,Paul

AU - Klasner,N.

AU - Wegener,I.

PB - Elsevier BV North-Holland

PY - 1999

Y1 - 1999

N2 - The following problem is known as group testing problem for n objects. Each object can be essential (defective) or non-essential (intact). The problem is to determine the set of essential objects by asking queries adaptively. A query can be identified with a set Q of objects and the query Q is answered by 1 if Q contains at least one essential object and by 0 otherwise. In the statistical setting the objects are essential, independently of each other, with a given probability p <1 while in the combinatorial setting the number k <n of essential objects is known. The cut-off point of statistical group testing is equal to p* = 12(3 - 5), i.e., the strategy of testing each object individually minimizes the average number of queries iff p >= p* or n = 1. In the combinatorial setting the worst case number of queries is of interest. It has been conjectured that the cut-off point of combinatorial group testing is equal to alpha* = 13, i.e., the strategy of testing n - 1 objects individually minimizes the worst case number of queries iff k/n >= alpha* and k <n. Some results in favor of this conjecture are proved.

AB - The following problem is known as group testing problem for n objects. Each object can be essential (defective) or non-essential (intact). The problem is to determine the set of essential objects by asking queries adaptively. A query can be identified with a set Q of objects and the query Q is answered by 1 if Q contains at least one essential object and by 0 otherwise. In the statistical setting the objects are essential, independently of each other, with a given probability p <1 while in the combinatorial setting the number k <n of essential objects is known. The cut-off point of statistical group testing is equal to p* = 12(3 - 5), i.e., the strategy of testing each object individually minimizes the average number of queries iff p >= p* or n = 1. In the combinatorial setting the worst case number of queries is of interest. It has been conjectured that the cut-off point of combinatorial group testing is equal to alpha* = 13, i.e., the strategy of testing n - 1 objects individually minimizes the worst case number of queries iff k/n >= alpha* and k <n. Some results in favor of this conjecture are proved.

UR - http://www2.imm.dtu.dk/pubdb/p.php?2081

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 1-3

VL - 91

SP - 83

EP - 92

ER -