Heuristic Methods for Top-k List Aggregation Under the Generalized Kendall Tau Distance
摘要
Top-k lists are a form of incomplete rankings in which only the best k items are ordered and a larger set of inferior items is unordered. Top-k list aggregation is the problem of combining several ranked top-k lists into a single consensus top-k ranking that best reflects all the input lists. This problem has wide-ranging applications such as information retrieval and recommendation systems. This work introduces heuristic algorithms to perform top-k aggregation under the generalized Kendall tau distance. In order to further improve the solutions obtained by these heuristics, it employs a local search post-processing algorithm. Furthermore, it develops a data reduction technique to facilitate the solution of large-scale instances.