Almost separable matrices

Matthew Aldridge, Leonardo Baldassini, Karen Gunderson

Research output: Contribution to journalArticle

11 Citations (Scopus)

Abstract

An m× n matrix A with column supports { Si} is k-separable if the disjunctions ⋃ i KSi are all distinct over all sets K of cardinality k. While a simple counting bound shows that m> klog 2n/ 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(klog 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 languageEnglish
Pages (from-to)215-236
Number of pages22
JournalJournal of Combinatorial Optimization
Volume33
Issue number1
Early online date12 Oct 2015
DOIs
Publication statusPublished - 1 Jan 2017

Keywords

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

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Almost separable matrices'. Together they form a unique fingerprint.

  • Cite this

    Aldridge, M., Baldassini, L., & Gunderson, K. (2017). Almost separable matrices. Journal of Combinatorial Optimization, 33(1), 215-236. https://doi.org/10.1007/s10878-015-9951-1