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

MP Kidd


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)=ΣΣγ(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.

Full Text:


DOI: https://doi.org/10.5784/26-2-91


  • There are currently no refbacks.

ISSN 2224-0004 (online); ISSN 0259-191X (print)

Powered by OJS and hosted by Stellenbosch University Library and Information Service since 2011.


This journal is hosted by the SU LIS on request of the journal owner/editor. The SU LIS takes no responsibility for the content published within this journal, and disclaim all liability arising out of the use of or inability to use the information contained herein. We assume no responsibility, and shall not be liable for any breaches of agreement with other publishers/hosts.

SUNJournals Help