The minimum number of codewords in a binary code with length n and covering radius R is denoted by K(n, R). The values of K(n, 1) are known up to length 8, and the corresponding optimal codes have been classified. It is known that 57/spl les/K(9, 1)/spl les/62. In the current work, the lower bound is improved to settle K(9, 1)=62. In the approach, which is computer-aided, possible distributions of codewords in subspaces are refined until each subspace is of dimension zero (consists of only one word). Repeatedly, a linear programming problem is solved considering only inequivalent distributions. A connection between this approach and weighted coverings is also presented; the computations give new results for such coverings as a by-product.

We derive several new lower bounds on the size of binary codes with covering radius one. In particular, we prove K