New constructions for covering designs

A(v, k, t) covering design, or covering, is a family of k-subnets, called blocks, chosen from a v-set, such that each t-subnet is contained in at least one of the blocks. The number of blocks is the covering's size, and the minimum size of such a covering is denoted by C(v,k,t). This paper gives three new methods for constructing good coverings; a greedy algorithm similar to Conway and Sloane's algorithm for lexicographic codes [6], and two methods that synthesize new coverings from preexisting ones. Using these new methods, together with results in the literature, we build tables of upper bounds on C(v,k,t) for v ? 32, k ? 16, and t ? 8. © 1995 John Wiley & Sons, Inc.     

New upper bounds on the minimum size of covering designs

Let D = {B₁, B₂,…, B_b} be a finite family of k-subsets (called blocks ) of a v-set X(v) = {1, 2,…, v} (with elements called points ). Then D is a (v, k, t) covering design or covering if every t-subset of X(v) is contained in at least one block of D. The number of blocks, b, is the size of the covering, and the minimum size of the covering is called the covering number , denoted C(v, k, t). This article is concerned with new constructions of coverings. The constructions improve many upper bounds on the covering number C(v, k, t) © 1998 John Wiley & Sons, Inc. J Combin Designs 6:21–41, 1998     

A tabu search algorithm for the covering design problem

A (v,k,t)-covering design is a collection of k-subsets (called blocks) of a v-set V{\mathcal{V}} such that every t-subset of V{\mathcal{V}} is contained in at least one block. Given v, k and t, the goal of the covering design problem is to find a covering made of a minimum number of blocks. In this paper, we present a new tabu algorithm for tackling this problem. Our algorithm exploits a new implementation designed in order to evaluate efficiently the performance of the neighbors of the current configuration. The new implementation is much less space-consuming than the currently used technique, making it possible to tackle much larger problem instances. It is also significantly faster. Thanks to these improved data structures, our tabu algorithm was able to improve the upper bound of more than 50 problem instances.     

The directed packing numbersDD(t,v, v), t≧4

A directed packing is a maximal collection ofk-subsets, called blocks, of a set of cardinalityv having the property that no orderedt-subset occurs in more than one block. A block contains an orderedt-set if its symbols appear, left to right, in the block. The cardinality of such a maximal collection is denoted byDD(t, k, v). We consider the special case whenk=v and derive some results on the sizes of maximal collections.     

3-(v, 4, 1) covering designs with chromatic numbers 2 and 3

A t-(v, k, λ) covering design is a pair (X, B) where X is a v-set and B is a collection of k-sets in X, called blocks, such that every t element subset of X is contained in at least λ blocks of B. The covering number, C_λ(t, k, v), is the minimum number of blocks a t-(v, k, λ) covering design may have. The chromatic number of (X, B) is the smallest m for which there exists a map φ: X → Z_m such that ∣φ((β)∣ ≥2 for all β ∈ B, where φ(β) = {φ(x): x ∈ β}. The system (X, B) is equitably m-chromatic if there is a proper coloring φ with minimal m for which the numbers ∣φ^?1(c)∣ c ∈ Z_m differ from each other by at most 1. In this article we show that minimum, (i.e., ∣B∣ = C λ (t, k, v)) equitably 3-chromatic 3-(v, 4, 1) covering designs exist for v ≡ 0 (mod 6), v ≥ 18 for v ≥ 1, 13 (mod 36), v ≡ 13 and for all numbers v = n, n + 1, where n ≡ 4, 8, 10 (mod 12), n ≥ 16; and n = 6.5^a 13^b 17^c ?4, a + b + c > 0, and n = 14, 62. We also show that minimum, equitably 2-chromatic 3-(v, 4, 1) covering designs exist for v ≡ 0, 5, 9 (mod 12), v ≥ 0, v = 2.5^a 13^b 17^c + 1, a + b + c > 0, and v = 23. © 1993 John Wiley & Sons, Inc.     

On maximal (k,t)-sets

Summary This investigation was originally motivated by the problem of determining the maximum number of points in finiten-dimensional projective spacePG(n, s) based on the Galois fieldGF(s) of orders=p ^h (wherep andh are positive integers andp is the prime characteristic of the field), such that not of these chosen points are linearly dependent. A set ofk distinct points inPG(n, s), not linearly dependent, is called a (k, t)-set fork ₁ >k. The maximum value ofk is denoted bym _t (n+1, s). The purpose of this paper is to find new upper bounds for some values ofn, s andt. These bounds are of importance in the experimental design and information theory problems.     

Covering Arrays of Strength Three

A covering array of size N, degree k, order v and strength t is a k × N array with entries from a set of v symbols such that in any t × N subarray every t × 1 column occurs at least once. Covering arrays have been studied for their applications to drug screening and software testing. We present explicit constructions and give constructive upper bounds for the size of a covering array of strength three.     

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.     

Sets in Abelian groups with distinct sums of pairs

A subset S={s₁,…,sk} of an Abelian group G is called an St-set of size k if all sums of t different elements in S are distinct. Let s(G) denote the cardinality of the largest S₂-set in G. Let v(k) denote the order of the smallest Abelian group for which s(G)?k. In this article, bounds for s(G) are developed and v(k) is determined for k?15 by computing s(G) for Abelian groups of order up to 183 using exhaustive backtrack search with isomorph rejection.     

Spectrum of resolvable directed quadruple systems

A t-(v, k, 1) directed design (or simply a t-(v, k, 1)DD) is a pair (S, ℐ), where S is a v-set and ℐ is a collection of k-tuples (called blocks) of S, such that every t-tuple of S belongs to a unique block. The t-(v, k, 1)DD is called resolvable if ℐ can be partitioned into some parallel classes, so that each parallel class is a partition of S. It is proved that a resolvable 3-(v, 4, 1)DD exists if and only if v = 0 (mod 4).     

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     

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.     

On directed designs with block size five

In at-(v, k,) directed design the blocks are orderedk-tuples and every orderedt-tuple of distinct points occurs in exactly blocks (as a subsequence). We studyt–(v, 5, 1) directed designs witht=3 andt=4. In particular, we construct the first known examples, and an infinite class, of 3-(v, 5, 1) directed designs, and the first known infinite class of 4-(v, 5, 1) directed designs.     

Combinatorial coverings from geometries over principal ideal rings

A t-(v, k, λ) covering is an incidence structure with v points, each block incident on exactly k points, such that every set of t distinct points is incident on at least λ blocks. By considering certain geometries over finite principal ideal rings, we construct infinite families of t-(v, k, λ) coverings having many interesting combinatorial properties. © 1999 John & Sons, Inc. J Combin Designs 7: 247–268, 1999     

Existence results for near resolvable designs

A near resolvable design, NRB(v, k), is a balanced incomplete block design whose block set can be partitioned into v classes such that each class contains every point of the design but one, and each point is missing from exactly one class. The necessary conditions for the existence of near resolvable designs are v ≡ 1 mod k and λ = k ? 1. These necessary conditions have been shown to be sufficient for k ? {2,3,4} and almost always sufficient for k ? {5,6}. We are able to show that there exists an integer n₀(k) so that NRB(v,k) exist for all v > n₀(k) and v ≡ 1 mod k. Using some new direct constructions we show that there are many k for which it is easy to compute an explicit bound on n₀(k). These direct constructions also allow us to build previously unknown NRB(v,5) and NRB(v,6). © 1995 John Wiley & Sons, Inc.     

Upper bounds on the general covering number Cλ(v,k, t,m)

A collection of k‐subsets (called blocks) of a v‐set X (v) = {1, 2,…, v} (with elements called points) is called a t‐(v, k, m, λ) covering if for every m‐subset M of X (v) there is a subcollection of with such that every block K ∈ has at least t points in common with M. It is required that v ≥ k ≥ t and v ≥ m ≥ t. The minimum number of blocks in a t‐(v, k, m, λ) covering is denoted by C_λ(v, k, t, m). We present some constructions producing the best known upper bounds on C_λ(v, k, t, m) for k = 6, a parameter of interest to lottery players. © 2004 Wiley Periodicals, Inc.     

Single change covering designs

A single-change covering designSC (v, k, b) on av-setV is a sequence ofb k-sets (blocks) onV which together cover every pair of elements ofV at least once, such that two successive blocks havek–1 elements in common. It is desirable to minimizeb. Some constructions and lower bounds forb are given.     

Incomplete perfect mendelsohn designs with block size 4 and one hole of size 7

Let v,k, and n be positive integers. An incomplete perfect Mendelsohn design, denoted by k-IPMD(v,n), is a triple (X, Y, ??) where X is a v-set (of points), Y is an n-subset of X, and ?? is a collection of cyclically ordered k-subsets of X (called blocks) such that every ordered pair (a, b) ∈ (X × X)?(Y × Y) appears t-apart in exactly one block of ?? and no ordered pair (a,b) ∈ Y × Y appears in any block of ?? for any t, where 1 ≤ t ≤ k ? 1. In this article, we obtain conclusive results regarding the existence of 4-IPMD(v,7) where the necessary conditions are v = 2 or 3(mod 4) and v ≥ 22. We also provide an application to the problem relating to coverings of PMDs with block size 4. © 1993 John Wiley & Sons, Inc.     

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.      

A lower bound for v in a t − (v,k, λ) design

In this paper it is shown that if v ? k + 1 then $\text{v ? t ? 1 + (k ? t + 1)(k ? t + 2)}\text{λ}$, where v, k, λ and t are the characteristic parameters of a t ? (v, k, λ) design. We compare this bound with the known lower bounds on v.