TY - JOUR

T1 - Partial covering arrays

T2 - Algorithms and asymptotics

AU - Sarkar, Kaushik

AU - Colbourn, Charles

AU - de Bonis, Annalisa

AU - Vaccaro, Ugo

N1 - Funding Information:
Acknowledgments Research of KS and CJC was supported in part by the National Science Foundation under Grant No. 1421058.
Publisher Copyright:
© Springer Science+Business Media New York 2017.

PY - 2018/5/27

Y1 - 2018/5/27

N2 - A covering arrayCA(N; t, k, v) is an N × k array with entries in {1,2,…,v}, for whichevery N × t subarray containseach t-tuple of {1,2,…,v}tamong 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}tneed only be contained among the rows ofat least(1 − ϵ) (Formula present) of the N × t subarrays and (2) the rows ofevery N × t subarray need only contain a (large)subsetof {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.

AB - A covering arrayCA(N; t, k, v) is an N × k array with entries in {1,2,…,v}, for whichevery N × t subarray containseach t-tuple of {1,2,…,v}tamong 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}tneed only be contained among the rows ofat least(1 − ϵ) (Formula present) of the N × t subarrays and (2) the rows ofevery N × t subarray need only contain a (large)subsetof {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.

KW - Combinatorial design

KW - Covering arrays

KW - Orthogonal arrays

KW - Partial covering arrays

KW - Software interaction testing

UR - http://www.scopus.com/inward/record.url?scp=85019747937&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85019747937&partnerID=8YFLogxK

U2 - 10.1007/s00224-017-9782-9

DO - 10.1007/s00224-017-9782-9

M3 - Article

AN - SCOPUS:85019747937

VL - 62

SP - 1470

EP - 1489

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 6

ER -