Abstract:
A round-robin tournament (or all-play-all tournament) is a competition “in which each con- testant plays all other contestants in turn”. The problem of ranking players in a round-robin tournament with a win or a loss outcome of every match is to rank players according to their performances in the tournament. This tournament structure also arises in other envi- ronments, for example, in the problems of soliciting customer preferences regarding a set of products, establishing funding priorities of a set of projects, establishing searching prior- ities for a set of search engines in the Internet. In this thesis, we have improved previously developed MST (Majority Spanning Tree) algorithm for solving this problem, where the number of violations has been chosen as the criterion of optimality. Whereas in previous MST algorithms a subset A of consecutively ranked players could be swapped with a subset B of consecutively ranked players, where A and B are consecutively ranked, in this improved version we have allowed A and B to be any disjoint subset. We also developed another Hy- brid algorithm using five related algorithms (Sort, Hamiltonian path, Arrange, MST and Improved MST) and compare the performance of these algorithms for the same sets of input data. Experimental results suggest that these new algorithm outperforms the existing ones.
