Two variants of the well known group testing problem are considered. In the first variant a finite set of items O and an unknown subset P of O are given, and one wants to identify the set P by asking the least number of questions of the form "Do Q and P share a single element?'', where Q is a subset of O. This problem naturally arises in the design of efficient contention resolution algorithms for certain random multiple-access communication systems [Berger et al. “Random multiple-access communication and group testing,” IEEE Trans. Commun., vol. 32, no. 7, pp. 769–779, 1984]. In the second variant of the problem, the answer to the question "Do Q and P share a single element?'' is correctly YES if Q and P intersect in a single element and NO if Q and P have an empty intersection, and it is left to a (possibly malicious) adversary otherwise. This model was introduced in [Damaschke, “Randomized group testing for mutually obscuring defectives,” Inf. Process. Lett., vol. 67, pp. 131–135, 1998] in the context of chemical compound testing. In this correspondence several algorithms for these group testing problems are presented, trying to optimize different measures of performance: The overall number of tests performed by the algorithm, the number of stages in which tests can be arranged, and the decoding complexity of identifying the elements of P from tests outcomes. Some of the given algorithms are optimal with respect to more than one of the above criteria. Instrumental to the results presented in the correspondence are new and improved bounds on certain generalization of superimposed codes introduced in [Dyachkov and Rykov, “A generalization of superimposed codes and its application to the multiple-access channel,” in Proc. 1984 IEEE Int. Symp. Inf. Theory, pp. 62–64], [De Bonis and Vaccaro, “Constructions of generalized superimposed codes with applications to group testing and conflict resolution in multiple access channels,” Theoretic. Comput. Sci., vol. 306, no. 1–3, pp. 223–243, 2003], a result that it is believed to be of independent interest.
Optimal Algorithms for Two Group Testing Problems and New Bounds on Generalized Superimposed Codes
DE BONIS, Annalisa;VACCARO, Ugo
2006-01-01
Abstract
Two variants of the well known group testing problem are considered. In the first variant a finite set of items O and an unknown subset P of O are given, and one wants to identify the set P by asking the least number of questions of the form "Do Q and P share a single element?'', where Q is a subset of O. This problem naturally arises in the design of efficient contention resolution algorithms for certain random multiple-access communication systems [Berger et al. “Random multiple-access communication and group testing,” IEEE Trans. Commun., vol. 32, no. 7, pp. 769–779, 1984]. In the second variant of the problem, the answer to the question "Do Q and P share a single element?'' is correctly YES if Q and P intersect in a single element and NO if Q and P have an empty intersection, and it is left to a (possibly malicious) adversary otherwise. This model was introduced in [Damaschke, “Randomized group testing for mutually obscuring defectives,” Inf. Process. Lett., vol. 67, pp. 131–135, 1998] in the context of chemical compound testing. In this correspondence several algorithms for these group testing problems are presented, trying to optimize different measures of performance: The overall number of tests performed by the algorithm, the number of stages in which tests can be arranged, and the decoding complexity of identifying the elements of P from tests outcomes. Some of the given algorithms are optimal with respect to more than one of the above criteria. Instrumental to the results presented in the correspondence are new and improved bounds on certain generalization of superimposed codes introduced in [Dyachkov and Rykov, “A generalization of superimposed codes and its application to the multiple-access channel,” in Proc. 1984 IEEE Int. Symp. Inf. Theory, pp. 62–64], [De Bonis and Vaccaro, “Constructions of generalized superimposed codes with applications to group testing and conflict resolution in multiple access channels,” Theoretic. Comput. Sci., vol. 306, no. 1–3, pp. 223–243, 2003], a result that it is believed to be of independent interest.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
