CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Threshold group testing (extended abstract)

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
Electronic Notes in Discrete Mathematics (1571-0653). Vol. 21 (2005), p. 265-271.
[Artikel, refereegranskad vetenskaplig]

We introduce a natural generalization of the well-studied group testing problem: A test gives a positive (negative) answer if the pool contains at least u (at most l) positive elements, and an arbitrary answer if the number of positive elements is between these fixed thresholds l and u. We show that the p positive elements can be determined up to a constant number of misclassifications, bounded by the gap between the thresholds. This is in a sense the best possible result. Then we study the number of tests needed to achieve this goal if n elements are given. If the gap is zero, the complexity is, similarly to classical group testing, O(p log n) for any fixed u. For the general case we propose a two-phase strategy consisting of a Distill and a Compress phase. We obtain some tradeoffs between classification accuracy and the number of tests. (Abstract of the full paper.)

Denna post skapades 2006-08-25. Senast ändrad 2015-02-11.
CPL Pubid: 6412