A covering array is an $N \times k$ array with each entry as one of $v$ symbols, where for every $t$ columns all possible $v^t$ tuples appears at least once. The covering array number (CAN) is the smallest $N$ for which a covering array exists, given $t, k, v$. Many known CANs are here.

I have been looking at "optimality" of covering arrays in the following sense: for known values of $N$, and given $v$ and $t$, compute $\frac{N}{v^t}$: call this the "ratio" of the covering array (code is here). From the code, I ordered all of the covering arrays by descending ratio. Surprisingly, the first 229 were covering arrays with $v=t=6$ (the highest ratio is ~829, and the 229th is ~549).

Is there a combinatorial aspect as to why this case is more difficult than any other one? There are several reasons as to why I believe this is so:

  • There are known constructions of covering arrays from perfect hash families for $v$ a prime power, and $6$ is not a prime power.
  • With higher values of $t$, computation time to reduce redundant rows (or general metaheuristics such as tabu search, simulated annealing, etc.) grows very large (not to mention the space needed).
  • Most studied cases are for lower values of $v,t$ (and only when $v=t=2$ are the optimal cases known).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.