Asymptotic and constructive methods for covering perfect hash families and covering arrays
Asymptotic and constructive methods for covering perfect hash families and covering arrays
复制标题
DOI：
10.1007/s10623-017-0369-x
复制
发表时间：
2018-04-01
影响因子：
1.6
通讯作者：
Sarkar, Kaushik
中科院分区：
文献类型：
--
作者：
Colbourn, Charles J.;Lanus, Erin;Sarkar, Kaushik
覆盖完美散列族紧凑地表示了某些覆盖数组。将两种概率方法应用于完全哈希族的覆盖，改进了v个符号、k列、强度t的覆盖阵列中最小行数的渐近上界，其中一个上界可以通过列重采样的随机多项式时间构造算法来实现，而另一个上界可以通过确定性多项式时间条件期望算法来实现。给出了这两种方法的计算结果。此外，在实践中，随机扩展算法进一步改进了覆盖数组的最佳已知大小。对于强度为7、强度为6、强度为5、强度为4的情况，使用列重采样和随机扩展的一组广泛的计算会产生明确的构造。当出现这种情况时，几乎所有已知的显式结构都会得到改进。为了增强性能，对覆盖完美散列族的限制确保了覆盖阵列中存在冗余行，这些冗余行可以删除。使用限制和随机扩展，在大多数情况下，对已知的显式结构的计算又一次改进。对强度3和强度4的计算表明，条件期望算法可以以更大的时间和存储投资为代价来产生进一步的改进。
Covering perfect hash families represent certain covering arrays compactly. Applying two probabilistic methods to covering perfect hash families improves upon the asymptotic upper bound for the minimum number of rows in a covering array with v symbols, k columns, and strength t. One bound can be realized by a randomized polynomial time construction algorithm using column resampling, while the other can be met by a deterministic polynomial time conditional expectation algorithm. Computational results are developed for both techniques. Further, a random extension algorithm further improves on the best known sizes for covering arrays in practice. An extensive set of computations with column resampling and random extension yields explicit constructions when for strength seven, for strength six, for strength five, and for strength four. When , almost all known explicit constructions are improved upon. For strength , restrictions on the covering perfect hash family ensure the presence of redundant rows in the covering array, which can be removed. Using restrictions and random extension, computations for and again improve upon known explicit constructions in the majority of cases. Computations for strengths three and four demonstrate that a conditional expectation algorithm can produce further improvements at the expense of a larger time and storage investment.