Ranking and Hillside Form
Marthe Fallang · Duo Research Archive (University of Oslo) · 2015
The first part of the thesis concerns the problem of ranking in general. We take a closer look at the two ranking methods; Elo rating and Colley rating. The former is used to rate and rank chess players, whereas the latter is used to rate and rank football teams. We also examine the ranking method PageRank, which is behind the search engine Google. Further, we study a ranking method presented in the article "A minimum violations ranking method" by K.E. Pedings, A.N. Langville and Y. Yamamoto. The authors define the concept of a hillside form for a square matrix, and present a ranking method that minimizes the number of violations from hillside form. Using this we construct a new notion, the distance from hillside form for a matrix, and use it to create a new ranking method that aims to find a hillside (or near-hillside) form for a matrix in a new way. We implement and test these ranking methods in MATLAB and OPL-CPLEX. Finally, we interpret ranking problems using the hillside form in the language of graph theory. We use this to connect the concept of a hillside form for a matrix to that of the topological ordering of the adjacency graph of that matrix.