Partial Covering Arrays: Algorithms and Asymptotics

A covering array CA(N;t, k, v) is an N×k array with entries in {1,2,...,v}, for which every N×t subarray contain seach t-tuple of {1,2,...,v}^t among its rows. Covering arrays find application in interaction testing, including software and hardware testing, advanced materials development, and biological systems. A central question is to determine or bound CAN(t, k, v), the minimum number N of rows of a CA(N;t, k, v).The well known bound CAN(t, k, v)=O((t−1)v^t logk) is not too far from being asymptotically optimal. Sensible relaxations of the covering requirement arise when (1) the set{1,2,...,v}^t need only be contained among the rows of at least(1−ε)C(k,t) of the N×t subarrays and (2) the rows of every N×t subarray need only contain a (large)subset of{1,2,...,v}^t. In this paper, using probabilistic methods, significant improvements on the covering array upper bound are established for both relaxations, and for the conjunction of the two. In each case, a randomized algorithm constructs such arrays in expected polynomial time.