Improved Combinatorial Group Testing Algorithms for Real-World Problem Sizes

Abstract

We study practically efficient methods for performing combinatorial group testing. We present efficient non-adaptive and two-stage combinatorial group testing algorithms, which identify the at most d items out of a given set of n items that are defective, using fewer tests for all practical set sizes. For example, our two-stage algorithm matches the information theoretic lower bound for the number of tests in a combinatorial group testing regimen.

18 pages; an abbreviated version of this paper is to appear at the 9th Worksh. Algorithms and Data Structures

Cited by in corpus (5)

• Noise-Resilient Group Testing: Limitations and Constructions
• Improved Adaptive Group Testing Algorithms with Applications to Multiple Access Channels and Dead Sensor Diagnosis
• A single-photon sampling architecture for solid-state imaging
• Structure-aware combinatorial group testing: a new method for pandemic screening
• From Discrepancy to Majority