Tracing a single user (Q850073)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5072609
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Tracing a single user |
scientific article; zbMATH DE number 5072609 |
Statements
Tracing a single user (English)
0 references
15 November 2006
0 references
Denote \(g(n,r)\) the maximum possible cardinality of a family of subsets of an \(n\)-element underlying set so that given a union of at most \(r\) members, one can identify at least one of the members. This has a close connection with the so-called group testing problem applied to design DNA chips in molecular biology. The paper shows that \(g(n,r)=2^{\Theta({n \over r})}.\) The main contribution of the paper is a new lower bound for \(g(n,r)\).
0 references
\(r\)-superimposed family
0 references
\(r\)-single-user-tracing superimposed family
0 references
group testing
0 references
0 references
0.8319218158721924
0 references
0.7412078380584717
0 references
0.7335931062698364
0 references
