Asymptotic size of covering arrays: an application of entropy compression

Abstract

A covering array $CA(N;t,k,v)$ is an $N\times k$ array $A$ whose each cell takes a value for a $v$-set $V$ called an alphabet. Moreover, the set $V^t$ is contained in the set of rows of every $N\times t$ subarray of $A$. The parameter $N$ is called the size of an array and $CAN(t,k,v)$ denotes the smallest $N$ for which a $CA(N;t,k,v)$ exists. It is well known that $CAN(t,k,v)=\mathrm{\Theta }({\log }_{2}k)$~\cite{godbole_bounds_1996}. In this paper we derive two upper bounds on $d(t,v)={\mathrm{limsup}}_{k\to \infty }\frac{CAN(t,k,v)}{{\log }_{2}k}$ using the algorithmic approach to the Lovász local lemma also known as entropy compression.

Submitted in January 2015

References in corpus (2)

• Entropy compression method applied to graph colorings
• Covering Array Bounds Using Analytical Techniques