Back to Search Start Over

Randomized post-optimization of covering arrays

Authors :
Nayeri, Peyman
Colbourn, Charles J.
Konjevod, Goran
Source :
European Journal of Combinatorics. Jan2013, Vol. 34 Issue 1, p91-103. 13p.
Publication Year :
2013

Abstract

Abstract: The construction of covering arrays with the fewest rows remains a challenging problem. Most computational and recursive constructions result in extensive repetition of coverage. While some is necessary, some is not. By reducing the repeated coverage, metaheuristic search techniques typically outperform simpler computational methods, but they have been applied in a limited set of cases. Time constraints often prevent them from finding an array of competitive size. We examine a different approach. Having used a simple computation or construction to find a covering array, we employ a post-optimization technique that repeatedly adjusts the array in an attempt to reduce its number of rows. At every stage the array retains full coverage. We demonstrate its value on a collection of previously best known arrays by eliminating, in some cases, 10% of their rows. In the well-studied case of strength two with twenty factors having ten values each, post-optimization produces a covering array with only 162 rows, improving on a wide variety of computational and combinatorial methods. We identify certain important features of covering arrays for which post-optimization is successful. [Copyright &y& Elsevier]

Details

Language :
English
ISSN :
01956698
Volume :
34
Issue :
1
Database :
Academic Search Index
Journal :
European Journal of Combinatorics
Publication Type :
Academic Journal
Accession number :
82111947
Full Text :
https://doi.org/10.1016/j.ejc.2012.07.017