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

Randomized group testing both query-optimal and minimal adaptive

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers)) ; Azam Sheikh Muhammad (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers))
Lecture Notes in Computer Science. SOFSEM 2012: Theory and practice of Computer Science. 38th Conference on Current Trends in Theory and Practice of Computer Science. Spindleruv Mlyn, Czech Republic, 21 - 27 January 2012 (0302-9743). Vol. 7147 (2012), p. 214-225.
[Konferensbidrag, refereegranskat]

The classical group testing problem asks to determine at most d defective elements in a set of n elements, by queries to subsets that return Yes if the subset contains some defective, and No if the subset is free of defectives. By the entropy lower bound, d log n tests are needed at least. We devise group testing strategies that combine two features: They achieve this optimal query bound asymptotically, with a factor 1+o(1) as n grows, and they work in a fixed number of stages of parallel queries. Our strategies are randomized and have a controlled failure probability, i.e., constant but arbitrarily small. We consider different settings (known or unknown d, probably correct or verified outcome), and we aim at the smallest possible number of stages. In particular, 2 stages are sufficient if d grows slowly enough with n, and 4 stages are sufficient if d=o(n).

Nyckelord: algorithmic learning theory, randomized algorithm, parallel queries, bioinformatics, group testing



Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2012-02-05. Senast ändrad 2015-02-11.
CPL Pubid: 154772

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)