2
$\begingroup$

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).
$\endgroup$

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.