Almost separable matrices

Matthew Aldridge; Leonardo Baldassini; Karen Gunderson

doi:10.1007/s10878-015-9951-1

Almost separable matrices

Matthew Aldridge^*, Leonardo Baldassini, Karen Gunderson

^*Corresponding author for this work

Research output: Contribution to journal › Article (Academic Journal) › peer-review

15 Citations (Scopus)

261 Downloads (Pure)

Abstract

An m x n matrix A with column supports {S_i} is k-separable if the disjunctions U_iε_kS_i are all distinct over all sets K of cardinality k. While a simple counting bound shows that m > klog₂n/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(n^1-β). 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	https://doi.org/10.1007/s10878-015-9951-1
Publication status	Published - Jan 2017

Keywords

Cover-free families
Disjunct matrices
Group testing
Probabilistic method
Separable matrices
Union-free families

Access to Document

10.1007/s10878-015-9951-1

Full-text PDF (accepted author manuscript)
This is the accepted author manuscript (AAM). The final published version (version of record) is available online via Springer Verlag at http://dx.doi.org/10.1007/s10878-015-9951-1. Please refer to any applicable terms of use of the publisher.
Accepted author manuscript, 501 KB

http://arxiv.org/abs/1410.1826

Handle.net

Persistent link

Cite this

@article{d23e21545ba14dfaab41c1405496d131,

title = "Almost separable matrices",

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 {\textquoteleft}almost k-separability{\textquoteright}, which requires that the disjunctions are {\textquoteleft}mostly distinct{\textquoteright}. 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.",

keywords = "Cover-free families, Disjunct matrices, Group testing, Probabilistic method, Separable matrices, Union-free families",

author = "Matthew Aldridge and Leonardo Baldassini and Karen Gunderson",

year = "2017",

month = jan,

doi = "10.1007/s10878-015-9951-1",

language = "English",

volume = "33",

pages = "215--236",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "1",

}

TY - JOUR

T1 - Almost separable matrices

AU - Aldridge, Matthew

AU - Baldassini, Leonardo

AU - Gunderson, Karen

PY - 2017/1

Y1 - 2017/1

N2 - 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.

AB - 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.

KW - Cover-free families

KW - Disjunct matrices

KW - Group testing

KW - Probabilistic method

KW - Separable matrices

KW - Union-free families

UR - http://www.scopus.com/inward/record.url?scp=84944705466&partnerID=8YFLogxK

U2 - 10.1007/s10878-015-9951-1

DO - 10.1007/s10878-015-9951-1

M3 - Article (Academic Journal)

SN - 1382-6905

VL - 33

SP - 215

EP - 236

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 1

ER -

Almost separable matrices

Abstract

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this