Graph domination, tabu search and the football pool problem (Q1356502): Difference between revisions

Finding the cardinality \(\rho_n\) of the smallest ternary code of length \(n\) with covering radius 1 is known as the football pool problem. The value of \(\rho_n\) is known for \(n\leq 5\) and \(n= \frac12 (3^k-1)\). The best upper bounds known at present were found by using simulated annealing or other heuristic algorithms combined with a theorem of \textit{A. Blokhuis} and \textit{C. W. H. Lam} [J. Comb. Theory, Ser. A 36, 240-244 (1984; Zbl 0533.05020)]. See also \textit{P. J. M. van Laarhoven, E. H. L. Aarts, J. H. van Lint} and \textit{L. T. Wille} [ibid., Ser. A 52, 304-312 (1989; Zbl 0724.90085)] and \textit{P. R. J. Östergård} [ibid., Ser. A 67, No. 2, 161-168 (1994; Zbl 0815.94023)]. The problem has been generalized to mixed covering codes as follows. Define \(K(t,b)\) to be the minimal cardinality of a subset \(C\) of \(\mathbb{Z}_3^t\times \mathbb{Z}_2^b\) such that every point in this set differs in at most one coordinate from a point in \(C\). So \(\rho_n= K(n,0)\). Tabu search is an approximation algorithm for combinatorial optimisation based on neighbourhood search. The power of this algorithm is tested by applying it to finding upper bounds for \(K(t,b)\). Several of the results referred to above are reproductd and the computing times are compared. Some of the results were found independently by \textit{P. R. J. Östergård} [`Constructing covering codes by tabu search'; preprint]. New bounds are given in the cases \(K(4,4)\), \(K(4,5)\), \(K(6,5)\), \(K(7,6)\), \(K(8,5)\), and \(K(9,3)\).