Randomized Postoptimization of Covering Arrays

Title: Randomized Postoptimization of Covering Arrays
Speaker: Charlie Colbourn
Time: 10:00am, Sunday, March 17th, 2013
Venue: Lecture Room, 3rd Floor, Building #5, State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences
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 postoptimization technique that repeatedly adjusts the array in order to (sometimes) 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, postoptimization 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 postoptimization is successful.

Biography:
Prof. Charles Colbourn is a Professor of Computer Science and Engineering in the School of Computing, Informatics and Decision Systems Engineering at Arizona State University. He has been in ASU since 2001. Right before that, from 1996 to 2001 he was the Dorothean Professor of Computer Science at the University of Vermont. His research concerns graph algorithms, combinatorial designs, and their applications. Prof. Colbourn has held faculty positions at the University of Saskatchewan, University of Waterloo, University of Vermont, and Arizona State University, as well as visiting positions at several other universities. He has been one of three editors-in-chief of the Journal of Combinatorial Designs since 1992. In 2004, the Institute of Combinatorics and its Applications named Prof. Colbourn as that year’s winner of Euler Medal for lifetime achievements in combinatorics.