Design and optimization of a general algorithm to calculate possible states of final tables of sport competitions

Abstract

The final positions in a particular single round-robin tournament can play a crucial role in the distribution of the participants' revenue, which would significantly influence the incomes of the tournament participants. So it would be of utmost importance to predict the final position of a participant at the end of a tournament. Determination of the possible states of a single round-robin final tournament table can provide a convenient way to ascertain what table data would be adequate to reach the desired position of a participant. In this thesis, to generate the possible states of a final tournament table, backward and forward approaches were proposed. The backward approach starts by generating a state of a final tournament table and ends with trying to build a tournament graph based on it, while the forward approach starts by generation a tournament graph and ends with concluding its corresponding state of tournament final table, in which the state is taken into account as a valid one if the participants' points are in descending order and the state is not previously found. General constraints related to the participants' points and their standings are proposed in this thesis to optimize the search space of each approach. Each participant holds a position in the final tournament table with which it is possible to determine its highest and lowest numbers of points. Optimized search spaces for each of the forward and backward approaches are proposed based on the highest and lowest possible numbers of points of the participants. To enhance the execution time of each approach, the performance of the used machine is exploited by implementing multi-threading based parallelization of the proposed optimized approaches.