Difference between revisions of "Open Problems:95"
m |
|||
| (2 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |||
|source=wola19 | |source=wola19 | ||
|who=Oliver Gebhard | |who=Oliver Gebhard | ||
}} | }} | ||
| − | In (non-adaptive) quantitative group testing, one has a population of n individuals, among which k=n^c (for some constant c\in(0,1)) are sick. The goal is to | + | In (non-adaptive) quantitative group testing, one has a population of n individuals, among which k=n^c (for some constant c\in(0,1)) are sick. The goal is to identify the k sick individuals by performing m non-adaptive tests. In each test, one specifies a subset S\subseteq [n] and learns whether S contains one or more sick individuals. |
By a counting argument, one gets a lower bound of m = \Omega\bigl( \frac{k}{\log k}\log \frac{n}{k} \bigr) tests; however, the best known upper bound is m = O( k\log \frac{n}{k} ). | By a counting argument, one gets a lower bound of m = \Omega\bigl( \frac{k}{\log k}\log \frac{n}{k} \bigr) tests; however, the best known upper bound is m = O( k\log \frac{n}{k} ). | ||
'''Question:''' Can one get rid of the \log k factor in the lower bound; or, conversely, improve the upper bound to match it? | '''Question:''' Can one get rid of the \log k factor in the lower bound; or, conversely, improve the upper bound to match it? | ||
Latest revision as of 20:40, 26 August 2019
| Suggested by | Oliver Gebhard |
|---|---|
| Source | WOLA 2019 |
| Short link | https://sublinear.info/95 |
In (non-adaptive) quantitative group testing, one has a population of n individuals, among which k=n^c (for some constant c\in(0,1)) are sick. The goal is to identify the k sick individuals by performing m non-adaptive tests. In each test, one specifies a subset S\subseteq [n] and learns whether S contains one or more sick individuals.
By a counting argument, one gets a lower bound of m = \Omega\bigl( \frac{k}{\log k}\log \frac{n}{k} \bigr) tests; however, the best known upper bound is m = O( k\log \frac{n}{k} ).
Question: Can one get rid of the \log k factor in the lower bound; or, conversely, improve the upper bound to match it?
