An Explicit Covering Array CA(411; 3, 11, 6) via Excursion-Capped Tabu Search
For integers $1 \le t \le k$ and $v \ge 2$, the covering array number $\mathrm{CAN}(t, k, v)$ is the minimum number of rows $N$ in an $N \times k$ array over $v$ symbols such that every $N \times t$ subarray contains all $v^t$ ordered $t$-tuples at least once. At $(t, k, v) = (3, 11, 6)$, standard tables record $\mathrm{CAN}(3, 11, 6) \le 420$, sharpened to $418$ via $\mathrm{PSL}(2, 5)$ orbit seeding and tabu repair and subsequently compressed to $416$ by multi-pass post-optimization of that $418$-row array. Starting from $\mathrm{CA}(418; 3, 11, 6)$, iterative row deletion and single-cell repair over a transposed tuple-index table yield an explicit, row-essential covering array $\mathrm{CA}(411; 3, 11, 6)$ establishing $\mathrm{CAN}(3, 11, 6) \le 411$: unweighted conflict-tabu search produces checkpoints down to $N = 412$, and two-stage WalkSAT-tabu plus excursion-capped tabu search---snapping back to the best near-covering array $A_{\mathrm{best}}$ once $n_{\mathrm{uncov}}(A) > E_{\max}$---closes $N = 412 \to 411$. We record elementary column-bonus early-abort bounds certifying exactness of the released solver's move-pruning loop and report a single-instance $24$-trial paired equal-step ablation on $N = 412 \to 411$, where excursion-capped snap-back improves best $n_{\mathrm{uncov}}$ over no-snap controls that stall early ($4/24$ vs.\ $0/24$ solved, paired McNemar $p = 0.125$) while dynamic tuple weighting provides no statistically significant benefit over unweighted snap-back.
Authors
- Kevin Grey (ORCID: https://orcid.org/0009-0007-8755-6501)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-10
- DOI
- https://doi.org/10.5281/zenodo.24096229
- Primary Topic
- Advanced Combinatorial Mathematics
- Type
- preprint