Graph domination, tabu search and the football pool problem
type: Item
instance of: scholarly article
title: Graph domination, tabu search and the football pool problem
zbMATH Open document ID: 0884.90125
DOI: 10.1016/S0166-218X(96)00049-2
author: Rowan Davies
author: Gordon Royle
published in: Discrete Applied Mathematics
publication date: 1998-04-05T00:00:00Z
full work available at URL: dam
review text: 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)\).
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 94B99
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 90C90
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1018581
zbMATH Keywords: football pool problem
zbMATH Keywords: mixed covering codes
zbMATH Keywords: tabu search
reviewed by: Jack van Lint
describes a project that uses: Tabu search
MaRDI profile type: Publication
cites work: Q4770409
cites work: More coverings by rook domains
cites work: Q4000288
cites work: Q4198056
cites work: A user's guide to tabu search
cites work: Q4354785
cites work: Upper bounds for football pool problems and mixed covering codes
cites work: A new upper bound for the football pool problem for nine matches
cites work: A new table of binary/ternary mixed covering codes
cites work: Q4222145
cites work: New upper bounds for the football pool problem for 11 and 12 matches
cites work: Q3809582
cites work: New upper bounds for the football pool problem for 6, 7, and 8 matches
cites work: The football pool problem for 6 matches: A new upper bound obtained by simulated annealing
description: scientific article; zbMATH DE number 1018581