Efficient algorithms using subiterative convergence for Kemeny ranking problem

Rank aggregation problem is useful to practitioners in political science, computer science, social science, medical science, and allied fields. The objective is to identify a consensus ranking of n objects that best fits independent rankings given by k different judges. Under the Kemeny framework, a distance metric called Kemeny distance is minimized to obtain consensus ranking. For large n, with present computing powers, it is not feasible to identify a consensus ranking under the Kemeny framework. To address the problem, researchers have proposed several algorithms. These algorithms are able to handle datasets with n up to 200 in a reasonable amount of time. However, run-time increases very quickly as n increases. In the present paper, we propose two basic algorithms- Subiterative Convergence and Greedy Algorithm. Using these basic algorithms, two advanced algorithms- FUR and SIgFUR have been developed. We show that our results are generally superior to existing algorithms in terms of both performance (Kemeny distance) and run-time. Even for large number of objects, the proposed algorithms run in few minutes. (C) 2018 Elsevier Ltd. All rights reserved