1. Partial Covering Arrays: Algorithms and Asymptotics.
- Author
-
Sarkar, Kaushik, Colbourn, Charles J., De Bonis, Annalisa, and Vaccaro, Ugo
- Subjects
- *
COMPUTER algorithms , *ASYMPTOTIC distribution , *PROBABILITY theory , *ORTHOGONAL arrays , *COMBINATORIAL designs & configurations - Abstract
A covering array CA(N;t, k, v) is an N × k array with entries in {1,2,…, v}, for which everyN × 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)vt log 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−휖)kt
of the N × t subarrays and (2) the rows of everyN × 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. [ABSTRACT FROM AUTHOR] - Published
- 2018
- Full Text
- View/download PDF