On the maximin algorithms for test allocations in partition testing

The proportional sampling (PS) strategy is a partition testing strategy tha t has been proved to have a better chance than random testing to detect at least one failure. A near proportional sampling (NPS) strategy is one that approximates the PS strategy when the latter is not feasible. We have earli er proved that the (basic) maximin algorithm generates a maximin test alloc ation, that is, an allocation of test cases that will maximally improve the lower bound performance of the partition testing strategy, and shown that the algorithm may serve as a systematic means of approximating the PS strat egy. in this paper, we derive the uniqueness and completeness conditions of generating maximin test allocations, propose the complete maximin algorith m that generates all possible maximin test allocations and demonstrate empi rically that the new algorithm is consistently better than random testing a s well as several other NPS strategies. (C) 2001 Elsevier Science B.V. All rights reserved.