2016/05/07 by Sarkar, Kaushik, Colbourn, Charles J., De Bonis, Annalisa +1
#05B30 (primary) #05B40 #05D40 #68R05 #68W20 (secondary) #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1605.02131
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 contains each 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)vtlog k) 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-ε)\binomkt 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.