Asymptotic Size of Covering Arrays: An Application of Entropy Compression |
| |
| Authors: | Nevena Franceti? Brett Stevens |
| |
| Institution: | 1. School of Mathematical Sciences, Monash University, Victoria, Australia;2. School of Mathematics and Statistics, Careleton University, Ottawa, ON, Canada |
| |
| Abstract: | A covering array  is an  array A such that each cell of A takes a value from a v‐set V, which is called the alphabet. Moreover, the set  is contained in the set of rows of every  subarray of A. The parameter N is called the size of an array and  denotes the smallest N for which a  exists. It is well known that  10]. In this paper, we derive two upper bounds on  using an algorithmic approach to the Lovász local lemma also known as entropy compression. |
| |
| Keywords: | |
|
|
is an 
array A such that each cell of A takes a value from a v‐set V, which is called the alphabet. Moreover, the set 
is contained in the set of rows of every 
subarray of A. The parameter N is called the size of an array and 
denotes the smallest N for which a 
exists. It is well known that 
10]. In this paper, we derive two upper bounds on 
using an algorithmic approach to the Lovász local lemma also known as entropy compression.