Title: Upper Bounds for Covering Designs by Simulated Annealing

Journal: Congressus Numerantium 96 (1993), 93-111.

A t-(v,m,k,\lambda ) covering design is a pair (X,A), where X is a set of v elements (called points) and A is a multiset of k-subsets of X (called blocks), such that every m-subset of X intersects at least \lambda members of A in at least t points. It is required that v >= k >= t and v >= m >= t. Such a covering design gives an upper bound on C_\lambda (v,m,k,t), the number of blocks in a minimal t-(v,m,k,\lambda ) covering design. In this paper it is shown how simulated annealing, a probabilistic method for solving combinatorial optimization problems, can be used to construct covering designs. Implementation of this method is discussed. The method is used to calculate new upper bounds on C_1(v,t,k,t) for k <= 9, v <= 13. A new exact value, C_1(11,4,6,4)=32, is obtained.