Efficient algorithms using subiterative convergence for Kemeny ranking problem
| Autor: | Prakash S. Badal, Ashish Das |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Theoretical computer science
General Computer Science MODELS 0211 other engineering and technologies 02 engineering and technology Aggregation problem Management Science and Operations Research 01 natural sciences Median ranking AXIOMATIC APPROACH 010104 statistics & probability Consensus ranking Convergence (routing) Heuristics 0101 mathematics Greedy algorithm Kemeny distance 021103 operations research Efficient algorithm Rank (computer programming) Ranking Modeling and Simulation DISTANCE Technical report Rank aggregation problem Kemeny-Snell distance |
| Zdroj: | IndraStra Global. |
| ISSN: | 2381-3652 |
| DOI: | 10.1002/2014GL060287 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|