A tabu-search for minimising the carry-over effects value of a round-robin tournament

Kidd, M. P. (2010)

CITATION: Kidd, M. P. 2010. A tabu-search for minimising the carry-over effects value of a round-robin tournament. ORiON, 26(2):125-141, doi:10.5784/26-2-91.

The original publication is available at http://orion.journals.ac.za


A player b in a round-robin sports tournament receives a carry-over effect from another player a if some third player opposes a in round i and b in round i + 1. Let γ_(ab) denote the number of times player b receives a carry-over effect from player a during a tournament. Then the carry-over effects value of the entire tournament T on n players is given by Г(T) = ∑^(n)_(i=1 ) ∑^(n)_(j=1) γ^(2)_(ij). Furthermore, let Г(n) denote the minimum carry-over effects value over all round-robin tournaments on n players. A strict lower bound on Г(n) is n(n 􀀀?????? 1) (in which case there exists a round-robin tournament of order n such that each player receives a carry- over effect from each other player exactly once), and it is known that this bound is attained for n = 2^r or n = 20, 22. It is also known that round-robin tournaments can be constructed from so-called starters; round-robin tournaments constructed in this way are called cyclic. It has previously been shown that cyclic round-robin tournaments have the potential of admitting small values for Г(T), and in this paper a tabu-search is used to find starters which produce cyclic tournaments with small carry-over effects values. The best solutions in the literature are matched for n ≤ 22, and new upper bounds are established on Г(n) for 24 ≤ n ≤ 40.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/21695
This item appears in the following collections: