Improved Combinatorial Group Testing Algorithms for Real-World Problem Sizes
<|reference_start|>Improved Combinatorial Group Testing Algorithms for Real-World Problem Sizes: 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.<|reference_end|>
@article{eppstein2005improved,
    title={Improved Combinatorial Group Testing Algorithms for Real-World Problem
  Sizes},
    author={David Eppstein, Michael T. Goodrich, and Daniel S. Hirschberg},
    journal={SIAM J. Computing 36(5):1360-1375, 2007},
    year={2005},
    doi={10.1137/050631847},
    archivePrefix={arXiv},
    eprint={cs/0505048},
    primaryClass={cs.DS}
}