Abstract
The classical group testing problem asks to determine at most d defective elements in a set of n elements, by queries to subsets that return Yes if the subset contains some defective, and No if the subset is free of defectives. By the entropy lower bound, \(\log_2\sum_{i=0}^d{n\choose i}\) tests, which is essentially dlog2 n, are needed at least. We devise group testing strategies that combine two features: They achieve this optimal query bound asymptotically, with a factor 1 + o(1) as n grows, and they work in a fixed number of stages of parallel queries. Our strategies are randomized and have a controlled failure probability, i.e., constant but arbitrarily small. We consider different settings (known or unknown d, probably correct or verified outcome), and we aim at the smallest possible number of stages. In particular, 2 stages are sufficient if d grows slowly enough with n, and 4 stages are sufficient if d = o(n).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ben-Gal, I.: An Upper Bound on the Weight-Balanced Testing Procedure with Multiple Testers. IIE Trans. 36, 481–493 (2004)
Chen, H.B., Hwang, F.K.: Exploring the Missing Link Among d-Separable, d̄-Separable and d-Disjunct Matrices. Discr. Appl. Math. 155, 662–664 (2007)
Cheng, Y., Du, D.Z.: New Constructions of One- and Two-Stage Pooling Designs. J. Comp. Biol. 15, 195–205 (2008)
Clementi, A.E.F., Monti, A., Silvestri, R.: Selective Families, Superimposed Codes, and Broadcasting on Unknown Radio Networks. In: SODA 2001, pp. 709–718. ACM/SIAM (2001)
Cormode, G., Muthukrishnan, S.: What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically. ACM Trans. Database Systems 30, 249–278 (2005)
Damaschke, P., Sheikh, M.A.: Competitive Group Testing and Learning Hidden Vertex Covers with Minimum Adaptivity. Discr. Math. Algor. Appl. 2, 291–311 (2010)
Damaschke, P., Muhammad, A.S.: Bounds for Nonadaptive Group Tests to Estimate the Amount of Defectives. In: Wu, W., Daescu, O. (eds.) COCOA 2010, Part II. LNCS, vol. 6509, pp. 117–130. Springer, Heidelberg (2010)
De Bonis, A., Gasieniec, L., Vaccaro, U.: Optimal Two-Stage Algorithms for Group Testing Problems. SIAM J. Comp. 34, 1253–1270 (2005)
De Bonis, A., Vaccaro, U.: Constructions of Generalized Superimposed Codes with Applications to Group Testing and Conflict Resolution in Multiple Access Channels. Theor. Comp. Sc. 306, 223–243 (2003)
Dorfman, R.: The Detection of Defective Members of Large Populations. The Annals of Math. Stat. 14, 436–440 (1943)
Du, D.Z., Hwang, F.K.: Pooling Designs and Nonadaptive Group Testing. Series on Appl. Math., vol. 18. World Scientific (2006)
Eppstein, D., Goodrich, M.T., Hirschberg, D.S.: Improved Combinatorial Group Testing Algorithms for Real-World Problem Sizes. SIAM J. Comp. 36, 1360–1375 (2007)
Goodrich, M.T., Hirschberg, D.S.: Improved Adaptive Group Testing Algorithms with Applications to Multiple Access Channels and Dead Sensor Diagnosis. J. Comb. Optim. 15, 95–121 (2008)
Hassin, R.: A Dichotomous Search for a Geometric Random Variable. Oper. Res. 32, 423–439 (1984)
He, Q.M., Gerchak, Y., Grosfeld-Nir, A.: Optimal Inspection Order When Process Failure Rate is Constant. Int. J. Reliability, Quality and Safety Eng. 3, 25–41 (1996)
Huffman, D.A.: A Method for the Construction of Minimum-Redundancy Codes. Proc. IRE 40, 1098–1101 (1952)
Iwen, M.A., Tewfik, A.H.: Adaptive Group Testing Strategies for Target Detection and Localization in Noisy Environments. IMA Preprint Series no. 2311. Univ. of Minnesota (2010)
Kahng, A.B., Reda, S.: New and Improved BIST Diagnosis Methods from Combinatorial Group Testing Theory. IEEE Trans. CAD of Integr. Circuits and Systems 25, 533–543 (2006)
Kainkaryam, R.M., Bruex, A., Gilbert, A.C., Schiefelbein, J., Woolf, P.J.: poolMC: Smart Pooling of mRNA Samples in Microarray Experiments. BMC Bioinf. 11, 299 (2010)
Kleinberg, J., Tardos, E.: Algorithm Design. Addison-Wesley, Boston (2006)
Kleitman, D.: On a Conjecture of Erdös–Katona on Commensurable Pairs Among Subsets of an n–Set. In: Erdös, P., Katona, G. (eds.) Theory of Graphs, Colloq. Proc., pp. 215–218. Akademiai Kiado, Budapest (1968)
Lubell, D.: A Short Proof of Sperner’s Lemma. J. Comb. Theory 1, 299 (1966)
Mézard, M., Toninelli, C.: Group Testing With Random Pools: Optimal Two-Stage Algorithms. IEEE Trans. Info. Th. 57, 1736–1745 (2011)
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge Univ. Press (1995)
Schlaghoff, J., Triesch, E.: Improved Results for Competitive Group Testing. Comb. Prob. and Comp. 14, 191–202 (2005)
Spencer, J.: Minimal Completely Separating Systems. J. Combin. Theory 8, 446–447 (1970)
Sperner, E.: Ein Satz über Untermengen einer endlichen Menge. Math. Zeitschrift 27, 544–548 (1928) (in German)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Damaschke, P., Muhammad, A.S. (2012). Randomized Group Testing Both Query-Optimal and Minimal Adaptive. In: Bieliková, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Turán, G. (eds) SOFSEM 2012: Theory and Practice of Computer Science. SOFSEM 2012. Lecture Notes in Computer Science, vol 7147. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-27660-6_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-27660-6_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-27659-0
Online ISBN: 978-3-642-27660-6
eBook Packages: Computer ScienceComputer Science (R0)