On the maximin algorithms for test allocations in partition testing

The proportional sampling (PS) strategy is a partition testing strategy that 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 earlier proved that the (basic) maximin algorithm generates a maximin test allocation, 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 strategy. In this paper, we derive the uniqueness and completeness conditions of generating maximin test allocations, propose the complete maximin algorithm that generates all possible maximin test allocations and demonstrate empirically that the new algorithm is consistently better than random testing as well as several other NPS strategies.