  A covering array $\mathsf{CA}(N;t,k,v)$ is an $N\times k$ array with entries
in $\{1, 2, \ldots , v\}$, for which every $N\times t$ subarray contains each
$t$-tuple of $\{1, 2, \ldots , 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 $\mathsf{CAN}(t,k,v)$, the minimum number $N$ of rows of
a $\mathsf{CA}(N;t,k,v)$. The well known bound
$\mathsf{CAN}(t,k,v)=O((t-1)v^t\log k)$ is not too far from being
asymptotically optimal. Sensible relaxations of the covering requirement arise
when (1) the set $\{1, 2, \ldots , v\}^t$ need only be contained among the rows
of at least $(1-\epsilon)\binom{k}{t}$ of the $N\times t$ subarrays and (2) the
rows of every $N\times t$ subarray need only contain a (large) subset of $\{1,
2, \ldots , 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.
