Upper bounds for covering arrays by tabu search

✍ Scribed by Kari J. Nurmela

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 208 KB
• Volume: 138
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00291-9

✦ Synopsis

A t-covering array is a collection of k vectors in a discrete space with the property that, in any t coordinate positions, all combinations of the coordinate values occur at least once. Such arrays have applications, for example, in software testing and data compression. Covering arrays are sometimes also called t-surjective arrays or qualitatively t-independent families; when t = 2 covering arrays are also called group covering designs or transversal covers. In an optimal covering array the number of vectors is minimized. Constructions for optimal covering arrays are known when t = 2 and the vectors are binary vectors, but in the other cases only upper and lower bounds are known. In this work a tabu search heuristic is used to construct covering arrays that improve on the previously known upper bounds on the sizes of optimal covering arrays.