Bounds for short covering codes and reactive tabu search

Given a prime power qq, cq(n,R)cq(n,R) denotes the minimum cardinality of a subset HH in Fqn such that every word in this space differs in at most RR coordinates from a multiple of a vector in HH. In this work, two new classes of short coverings are established. As an application, a new optimal record-breaking result on the classical covering code is obtained by using short covering. We also reformulate the numbers cq(n,R)cq(n,R) in terms of dominating set on graphs. Departing from this reformulation, the reactive tabu search (a variation of tabu search heuristics) is developed to obtain new upper bounds on cq(n,R)cq(n,R). The algorithm is described and conclusions on the results are drawn; they identify the advantages of using the reactive mechanism for this problem. Tables of lower and upper bounds on cq(n,R)cq(n,R), q=3,4q=3,4, n≤7n≤7, and R≤3R≤3, are also presented.