A tabu-search for minimising the carry-over effects value of a round-robin tournament
AbstractA 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)=Î£Î£Î³(ij)^2. 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.
The following license applies:
Attribution CC BY
This license lets others distribute, remix, tweak, and build upon your work, even commercially, as long as they credit you for the original creation.