Covering and radius-covering arrays: Constructions and classification

The minimum number of rows in covering arrays (equivalently, surjective codes) and radius-covering arrays (equivalently, surjective codes with a radius) has been determined precisely only in special cases. In this paper, explicit constructions for numerous best known covering arrays (upper bounds) are found by a combination of combinatorial and computational methods. For radius-covering arrays, explicit constructions from covering codes are developed. Lower bounds are improved upon using connections to orthogonal arrays, partition matrices, and covering codes, and in specific cases by computation. Consequently for some parameter sets the minimum size of a covering array is determined precisely. For some of these, a complete classification of all inequivalent covering arrays is determined, again using computational techniques. Existence tables for up to 10 columns, up to 8 symbols, and all possible strengths are presented to report the best current lower and upper bounds, and classifications of inequivalent arrays.     

Constructing strength three covering arrays with augmented annealing

A covering arrayCA(N;t,k,v) is an N×k array such that every N×t sub-array contains all t-tuples from v symbols at least once, where t is the strength of the array. One application of these objects is to generate software test suites to cover all t-sets of component interactions. Methods for construction of covering arrays for software testing have focused on two main areas. The first is finding new algebraic and combinatorial constructions that produce smaller covering arrays. The second is refining computational search algorithms to find smaller covering arrays more quickly. In this paper, we examine some new cut-and-paste techniques for strength three covering arrays that combine recursive combinatorial constructions with computational search; when simulated annealing is the base method, this is augmented annealing. This method leverages the computational efficiency and optimality of size obtained through combinatorial constructions while benefiting from the generality of a heuristic search. We present a few examples of specific constructions and provide new bounds for some strength three covering arrays.     

Linear hash families and forbidden configurations

The classical orthogonal arrays over the finite field underlie a powerful construction of perfect hash families. By forbidding certain sets of configurations from arising in these orthogonal arrays, this construction yields previously unknown perfect, separating, and distributing hash families. When the strength s of the orthogonal array, the strength t of the hash family, and the number of its rows are all specified, the forbidden sets of configurations can be determined explicitly. Each forbidden set leads to a set of equations that must simultaneously hold. Hence computational techniques can be used to determine sufficient conditions for a perfect, separating, and distributing hash family to exist. In this paper the forbidden configurations, resulting equations, and existence results are determined when (s, t) ∈ {(2, 5), (2, 6), (3, 4), (4, 3)}. Applications to the existence of covering arrays of strength at most six are presented.      

Efficient algorithmic implementation of the Voigt/complex error function based on exponential series approximation

We show that a Fourier expansion of the exponential multiplier yields an exponential series that can compute high-accuracy values of the complex error function in a rapid algorithm. Numerical error analysis and computational test reveal that with essentially higher accuracy it is as fast as FFT-based Weideman’s algorithm at a regular size of the input array and considerably faster at an extended size of the input array. As this exponential series approximation is based only on elementary functions, the algorithm can be implemented utilizing freely available functions from the standard libraries of most programming languages. Due to its simplicity, rapidness, high-accuracy and coverage of the entire complex plane, the algorithm is efficient and practically convenient in numerical methods related to the spectral line broadening and other applications requiring error-function evaluation over extended input arrays.     

Children’s conceptions on the structure of an array: Using quick images as a gateway to multiplicative ideas

In this paper we report the conceptions about arrays that came to the fore as one class of second-grade students participated in whole classroom discussions and activities focused on the structure of arrays presented as a Quick Images routine. Before the intervention, students were not introduced to formal multiplication but had completed a unit on arrays. A constant comparative method was used to identify numeric and spatial structuring strategies that allowed for students’ conceptions about the structure of the array to emerge. Results indicated that not all students automatically use arrays as a composite of rows. We found that the use of Quick Images with larger arrays and non-arrays within the whole classroom discussion was successful at eliciting and directing students’ attention towards the spatial features of an array, including seeing an array as made of a composite of rows (or columns).     

Covering arrays of higher strength from permutation vectors

A covering array CA(N;t,k,v) is an N × k array such that every N × t sub‐array contains all t‐tuples from v symbols at least once, where t is the strength of the array. Covering arrays are used to generate software test suites to cover all t‐sets of component interactions. We introduce a combinatorial technique for their construction, focussing on covering arrays of strength 3 and 4. With a computer search, covering arrays with improved parameters have been found. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 202–213, 2006     

Asymptotic and constructive methods for covering perfect hash families and covering arrays

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 \(k \le 75\) for strength seven, \(k \le 200\) for strength six, \(k \le 600\) for strength five, and \(k \le 2500\) for strength four. When \(v > 3\), almost all known explicit constructions are improved upon. For strength \(t=3\), 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 \(t=3\) and \(k \le 10{,}000\) 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.     

Products of mixed covering arrays of strength two

A covering array CA(N;t,k, v is an N × k array such that every N × t subarray contains all t‐tuples from v symbols at least once, where t is the strength of the array. Covering arrays are used to generate software test suites to cover all t‐sets of component interactions. The particular case when t = 2 (pairwise coverage) has been extensively studied, both to develop combinatorial constructions and to provide effective algorithmic search techniques. In this paper, a simple “cut‐and‐paste” construction is extended to covering arrays in which different columns (factors) admit different numbers of symbols (values); in the process an improved recursive construction for covering arrays with t = 2 is derived. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 124–138, 2006     

Constructions of covering arrays of strength five

A covering array of size N, strength t, degree k and order v, or a CA(N; t, k, v) in short, is an N × k array on v symbols. In every N × t subarray, each t-tuple occurs in at least one row. Covering arrays have been studied for their significant applications to generating software test suites to cover all t-sets of component interactions. In this paper, we present two constructive methods to obtain covering arrays of strength 5 by using difference covering arrays and holey difference matrices with a prescribed property. As a consequence, some new upper bounds on the covering numbers are derived.     

Constructing heterogeneous hash families by puncturing linear transversal designs

Constructions that use hash families to select columns from small covering arrays in order to construct larger ones can exploit heterogeneity in the numbers of symbols in the rows of the hash family. For specific distributions of numbers of symbols, the efficacy of the construction is improved by accommodating more columns in the hash family. Known constructions of such heterogeneous hash families employ finite geometries and their associated transversal designs. Using thwarts in transversal designs, specific constructions of heterogeneous hash families are developed, and some open questions are posed.     

Generalized latin matrix and construction of orthogonal arrays

In this paper, generalized Latin matrix and orthogonal generalized Latin matrices are proposed. By using the property of orthogonal array, some methods for checking orthogonal generalized Latin matrices are presented. We study the relation between orthogonal array and orthogonal generalized Latin matrices and obtain some useful theorems for their construction. An example is given to illustrate applications of main theorems and a new class of mixed orthogonal arrays are obtained.     

Roux-type constructions for covering arrays of strengths three and four

A covering array CA(N;t,k,v) is an N × k array such that every N × t sub-array contains all t-tuples from v symbols at least once, where t is the strength of the array. Covering arrays are used to generate software test suites to cover all t-sets of component interactions. Recursive constructions for covering arrays of strengths 3 and 4 are developed, generalizing many “Roux-type” constructions. A numerical comparison with current construction techniques is given through existence tables for covering arrays.      

Residual scaling techniques in multigrid, II: Practical applications

This paper focuses on the practical applications of the multigrid residual scaling techniques and is the continuation of a companion paper: Residual scaling techniques in multigrid, I: Equivalence proof [Appl. Math. Comput. 86:283–303 (1997)]. We discuss the computational issues of some residual scaling techniques which have been proven mathematically equivalent. A heuristic residual analysis technique, based on the geometry of the grid points and the relaxation pattern, is introduced to estimate the optimal residual scaling factor for a high-order multigrid method. We compare the performance of a typical pre-optimization (pre-acceleration) technique with a typical post-optimization (post-acceleration) technique and show that the pre-optimization is preferable in both convergence and efficiency. Our numerical results support the theoretical conclusions made in the companion paper and demonstrate the full advantage of the pre-optimization technique over the post-optimization technique.     

Mixed covering arrays on graphs

Covering arrays have applications in software, network and circuit testing. In this article, we consider a generalization of covering arrays that allows mixed alphabet sizes as well as a graph structure that specifies the pairwise interactions that need to be tested. Let k and n be positive integers, and let G be a graph with k vertices v₁,v₂,…, v_k with respective vertex weights g₁ ≤ g₂ ≤ … ≤ g_k. A mixed covering array on G, denoted by , is an n × k array such that column i corresponds to v_i, cells in column i are filled with elements from ?_gi and every pair of columns i,j corresponding to an edge v_i,v_j in G has every possible pair from ?_gi × ?_gj appearing in some row. The number of rows in such array is called its size. Given a weighted graph G, a mixed covering array on G with minimum size is called optimal. In this article, we give upper and lower bounds on the size of mixed covering arrays on graphs based on graph homomorphisms. We provide constructions for covering arrays on graphs based on basic graph operations. In particular, we construct optimal mixed covering arrays on trees, cycles and bipartite graphs; the constructed optimal objects have the additional property of being nearly point balanced. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 393–404, 2007     

An identity of Andrews and a new method for the Riordan array proof of combinatorial identities

We consider an identity relating Fibonacci numbers to Pascal's triangle discovered by G.E. Andrews. Several authors provided proofs of this identity, most of them rather involved or else relying on sophisticated number theoretical arguments. We present a new proof, quite simple and based on a Riordan array argument. The main point of the proof is the construction of a new Riordan array from a given Riordan array, by the elimination of elements. We extend the method and as an application we obtain other identities, some of which are new. An important feature of our construction is that it establishes a nice connection between the generating function of the A-sequence of a certain class of Riordan arrays and hypergeometric functions.     

Refining invariants for computing autotopism groups of partial Latin rectangles

Prior to using computational tools that find the autotopism group of a partial Latin rectangle (its stabilizer group under row, column and symbol permutations), it is beneficial to find partitions of the rows, columns and symbols that are invariant under autotopisms and are as fine as possible. We look at the lattices formed by these partitions and introduce two invariant refining maps on these lattices. The first map generalizes the strong entry invariant in a previous work. The second map utilizes some bipartite graphs, introduced here, whose structure is determined by pairs of rows (or columns, or symbols). Experimental results indicate that in most cases (ordinarily 99%+), the combined use of these invariants gives the theoretical best partition of the rows, columns and symbols, outperforms the strong entry invariant, which only gives the theoretical best partitions in roughly 80% of the cases.     

Generalized covering designs and clique coverings

Inspired by the “generalized t‐designs” defined by Cameron [P. J. Cameron, Discrete Math 309 (2009), 4835–4842], we define a new class of combinatorial designs which simultaneously provide a generalization of both covering designs and covering arrays. We then obtain a number of bounds on the minimum sizes of these designs, and describe some methods of constructing them, which in some cases we prove are optimal. Many of our results are obtained from an interpretation of these designs in terms of clique coverings of graphs. © 2011 Wiley Periodicals, Inc. J Combin Designs 19:378‐406, 2011     

Minimizing total tardiness in parallel machine scheduling with setup times: An adaptive memory-based GRASP approach

This paper deals with the problem of scheduling jobs in uniform parallel machines with sequence-dependent setup times in order to minimize the total tardiness relative to job due dates. We propose GRASP versions that incorporate adaptive memory principles for solving this problem. Long-term memory is used in the construction of an initial solution and in a post-optimization procedure which connects high quality local optima by means of path relinking. Computational tests are carried out on a set of benchmark instances and the proposed GRASP versions are compared with heuristic methods from the literature.     

Bi-criteria optimization problems for decision rules

We consider bi-criteria optimization problems for decision rules and rule systems relative to length and coverage. We study decision tables with many-valued decisions in which each row is associated with a set of decisions as well as single-valued decisions where each row has a single decision. Short rules are more understandable; rules covering more rows are more general. Both of these problems—minimization of length and maximization of coverage of rules are NP-hard. We create dynamic programming algorithms which can find the minimum length and the maximum coverage of rules, and can construct the set of Pareto optimal points for the corresponding bi-criteria optimization problem. This approach is applicable for medium-sized decision tables. However, the considered approach allows us to evaluate the quality of various heuristics for decision rule construction which are applicable for relatively big datasets. We can evaluate these heuristics from the point of view of (i) single-criterion—we can compare the length or coverage of rules constructed by heuristics; and (ii) bi-criteria—we can measure the distance of a point (length, coverage) corresponding to a heuristic from the set of Pareto optimal points. The presented results show that the best heuristics from the point of view of bi-criteria optimization are not always the best ones from the point of view of single-criterion optimization.