Asymptotic size of covering arrays: an application of entropy compression

DOI10.1002/JCD.21553MaRDI QIDQ5349280zbMATH OpenOpenAlexFDO

Authors Nevena Francetić, Brett Stevens

Publication date 24 August 2017

Published in Journal of Combinatorial Designs (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.08876

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Combinatorial aspects of packing and covering (05B40)

Abstract: A covering array $CA(N;t,k,v)$ is an $Nimesk$ 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 $Nimest$ 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)=mTheta(lo{g}_{2}k)$~cite{godbole_bounds_1996}. In this paper we derive two upper bounds on $d(t,v)=limsu{p}_{kightarrowinfty}fracCAN(t,k,v)lo{g}_{2}k$ using the algorithmic approach to the Lov'{a}sz local lemma also known as entropy compression.

Recommendations

• Covering array bounds using analytical techniques
• Upper bounds on the size of covering arrays
• Small arrays of maximum coverage

Cited in

(10)

• On a combinatorial framework for fault characterization
• Asymptotic and constructive methods for covering perfect hash families and covering arrays
• The Lovász local lemma and variable strength covering arrays
• Entropy compression versus Lovász local lemma
• Upper bounds on the sizes of variable strength covering arrays using the Lovász local lemma
• Moser-Tardos resampling algorithm, entropy compression method and the subset gas
• Covering array bounds using analytical techniques
• Upper bounds on the size of covering arrays
• t-covering arrays generated by a tiling probability model
• Maximum shattering

This page was built for publication: Asymptotic size of covering arrays: an application of entropy compression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5349280)