About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
IEEE INFOCOM 1992
Conference paper
A new competitive algorithm for group testing
Abstract
Algorithms for the group testing problem when there is no a priori information on the number of defective items are considered. The efficiency criterion used in the competitive ratio, which is the ratio of the number of tests required by an algorithm when there is no a priori information on the number of defective items, to the number of tests required by an optimal algorithm when the number of defective items is known in advance. A new algorithm is presented, and it is shown that the competitive ratio of this algorithm is 2. This result is an improvement over an algorithm given by D.Z. Du et al. (1991), for which the competitive ratio was 2.75. It also proves a conjecture made by them. A new application of group testing techniques for high-speed networks is discussed. © 1992 IEEE.