Asymptotic Size of Covering Arrays: An Application of Entropy Compression. Issue 6 (2nd January 2017)

• Record Type: Journal Article
• Authors: Francetić, Nevena; Stevens, Brett
• Is Part Of: Journal of combinatorial designs. Volume 25:Issue 6(2017:Jun.)
• Page Start: 243
• Page End: 257
• Publication Date: 2017-01-02
• Subjects: Combinatorial designs and configurations -- Periodicals; Configurations et schémas combinatoires -- Périodiques; 511.6
• DOI: 10.1002/jcd.21553
• Languages: English
• ISSNs: 1063-8539

Abstract

Abstract: A covering array CA ( N ; t, k, v ) is an N × k array A such that each cell of A takes a value from a v ‐set V, which is called the alphabet. Moreover, the set V t 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 ) = Θ ( log 2 k ) [10]. In this paper, we derive two upper bounds on d ( t, v ) = lim sup k → ∞ CAN ( t, k, v ) log 2 k using an algorithmic approach to the Lovász local lemma also known as entropy compression.