Abstract
An m x n matrix A with column supports {Si} is k-separable if the disjunctions UiεkSi are all distinct over all sets K of cardinality k. While a simple counting bound shows that m > klog2n/k rows are required for a separable matrix to exist, in fact it is necessary for m to be about a factor of k more than this. In this paper, we consider a weaker definition of ‘almost k-separability’, which requires that the disjunctions are ‘mostly distinct’. We show using a random construction that these matrices exist with m = O(k log n) rows, which is optimal for k = O(n1-β). Further, by calculating explicit constants, we show how almost separable matrices give new bounds on the rate of nonadaptive group testing.
Original language | English |
---|---|
Pages (from-to) | 215-236 |
Number of pages | 22 |
Journal | Journal of Combinatorial Optimization |
Volume | 33 |
Issue number | 1 |
Early online date | 12 Oct 2015 |
DOIs | |
Publication status | Published - Jan 2017 |
Keywords
- Cover-free families
- Disjunct matrices
- Group testing
- Probabilistic method
- Separable matrices
- Union-free families