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

**Harvard**

Sheikh Muhammad, A. (2011) *Engineering Competitive and Query-Optimal Minimal-Adaptive Randomized Group Testing Strategies*. Göteborg : Chalmers University of Technology (Technical report L - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University, nr: 81L).

** BibTeX **

@book{

Sheikh Muhammad2011,

author={Sheikh Muhammad, Azam},

title={Engineering Competitive and Query-Optimal Minimal-Adaptive Randomized Group Testing Strategies},

abstract={Suppose that given is a collection of $n$ elements where $d$ of them are \emph{defective}. We can query an arbitrarily chosen subset of elements which returns Yes if the subset contains at least one defective and No if the subset is free of defectives.
The problem of group testing is to identify the defectives with a minimum number of such queries.
By the information-theoretic lower bound at least $\log_2 \binom {n}{d} \approx d\log_2 (\frac{n}{d}) \approx d\log_2 n$ queries are needed. Using adaptive group testing, i.e., asking one query at a time, the lower bound can be easily achieved. However, strategies are preferred that work in a fixed small number of stages, where queries in a stage are asked in parallel. A group testing strategy is called \emph{competitive} if it works for completely unknown $d$ and requires only $O(d\log_2 n)$ queries. Usually competitive group testing is based on sequential queries. We have shown that actually competitive group testing with expected $O(d\log_2 n)$ queries is possible in only $2$ or $3$ stages. Then we have focused on minimizing the hidden constant factor in the query number and proposed a systematic approach for this purpose.
Another main result is related to the design of query-optimal and minimal-adaptive strategies. We have shown that a $2$-stage randomized strategy with prescribed success probability can asymptotically achieve the information-theoretic lower bound for $d \ll n$ and growing much slower than $n$. Similarly, we can approach the entropy lower bound in $4$ stages when $d=o(n)$. },

publisher={Institutionen för data- och informationsteknik, Datavetenskap (Chalmers), Chalmers tekniska högskola,},

place={Göteborg},

year={2011},

series={Technical report L - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University, no: 81L},

keywords={group testing; pooling design; combinatorial search; learning by queries; randomization; competitive ratio; linear program},

note={121},

}

** RefWorks **

RT Dissertation/Thesis

SR Electronic

ID 140504

A1 Sheikh Muhammad, Azam

T1 Engineering Competitive and Query-Optimal Minimal-Adaptive Randomized Group Testing Strategies

YR 2011

AB Suppose that given is a collection of $n$ elements where $d$ of them are \emph{defective}. We can query an arbitrarily chosen subset of elements which returns Yes if the subset contains at least one defective and No if the subset is free of defectives.
The problem of group testing is to identify the defectives with a minimum number of such queries.
By the information-theoretic lower bound at least $\log_2 \binom {n}{d} \approx d\log_2 (\frac{n}{d}) \approx d\log_2 n$ queries are needed. Using adaptive group testing, i.e., asking one query at a time, the lower bound can be easily achieved. However, strategies are preferred that work in a fixed small number of stages, where queries in a stage are asked in parallel. A group testing strategy is called \emph{competitive} if it works for completely unknown $d$ and requires only $O(d\log_2 n)$ queries. Usually competitive group testing is based on sequential queries. We have shown that actually competitive group testing with expected $O(d\log_2 n)$ queries is possible in only $2$ or $3$ stages. Then we have focused on minimizing the hidden constant factor in the query number and proposed a systematic approach for this purpose.
Another main result is related to the design of query-optimal and minimal-adaptive strategies. We have shown that a $2$-stage randomized strategy with prescribed success probability can asymptotically achieve the information-theoretic lower bound for $d \ll n$ and growing much slower than $n$. Similarly, we can approach the entropy lower bound in $4$ stages when $d=o(n)$.

PB Institutionen för data- och informationsteknik, Datavetenskap (Chalmers), Chalmers tekniska högskola,

T3 Technical report L - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University, no: 81L

LA eng

LK http://www.cse.chalmers.se/~azams/lic/azams_licthesis.pdf

OL 30