### Skapa referens, olika format (klipp och klistra)

**Harvard**

Damaschke, P. (2011) *Optimal randomized group testing: A canonical form and the one-defective case*.

** BibTeX **

@conference{

Damaschke2011,

author={Damaschke, Peter},

title={Optimal randomized group testing: A canonical form and the one-defective case},

booktitle={ICALP 2011 Workshop on Algorithms and Data Structures for Selection, Identification and Encoding ICALP2011GT},

pages={55-67},

abstract={For the well-established group testing problem, i.e., finding defective elements in a set by testing subsets for the presence of defectives, asymptotic bounds on the test number are known for various models, but they do not yield optimal test strategies for specific instance sizes. Here we quest for provably optimal group testing strategies for a given input size, number of defectives, and number of stages of parallel tests. Especially for small instances, randomized strategies can significantly save tests on average, compared to deterministic strategies in the worst case. We show that randomization can be restricted to some canonical form. This greatly simplifies the construction of optimal randomized strategies. To demonstrate the power of this canonical form, we apply this result to the case of one
defective, i.e., find the single defective and verify that it is the only one. We solve the case of one defective and two stages completely, subject to a problem in extremal combinatorics related to Sperner's theorem. Worst-case
optimal strategies for one defective can be implemented in only two stages.
For adaptive group testing with one defective we also get optimal randomized strategies.},

year={2011},

}

** RefWorks **

RT Conference Proceedings

SR Print

ID 144340

A1 Damaschke, Peter

T1 Optimal randomized group testing: A canonical form and the one-defective case

YR 2011

T2 ICALP 2011 Workshop on Algorithms and Data Structures for Selection, Identification and Encoding ICALP2011GT

SP 55

OP 67

AB For the well-established group testing problem, i.e., finding defective elements in a set by testing subsets for the presence of defectives, asymptotic bounds on the test number are known for various models, but they do not yield optimal test strategies for specific instance sizes. Here we quest for provably optimal group testing strategies for a given input size, number of defectives, and number of stages of parallel tests. Especially for small instances, randomized strategies can significantly save tests on average, compared to deterministic strategies in the worst case. We show that randomization can be restricted to some canonical form. This greatly simplifies the construction of optimal randomized strategies. To demonstrate the power of this canonical form, we apply this result to the case of one
defective, i.e., find the single defective and verify that it is the only one. We solve the case of one defective and two stages completely, subject to a problem in extremal combinatorics related to Sperner's theorem. Worst-case
optimal strategies for one defective can be implemented in only two stages.
For adaptive group testing with one defective we also get optimal randomized strategies.

LA eng

OL 30