Asymptotic size of covering arrays: an application of entropy compression
Francetić, Nevena · Stevens, Brett
Original · EN
A covering array CA(N; t,k,v) is an N × k array A whose each cell takes a value for a v-set V called an alphabet. Moreover, the set Vᵗ is contained in the set of rows of every N × 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) = Θ(₂ k) godbolebounds₁996. In this paper we derive two upper bounds on d(t,v)=ₖ → ∞ CAN(t,k,v)/₂ k using the algorithmic approach to the Lovász local lemma also known as entropy compression.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.