Rank aggregation in cyclic sequences

Abstract

In this paper we propose the problem of finding the cyclic sequence which best represents a set of cyclic sequences. Given a set of elements and a precedence cost matrix we look for the cyclic sequence of the elements which is at minimum distance from all the ranks when the permutation metric distance is the Kendall Tau distance. In other words, the problem consists of finding a robust cyclic rank with respect to a set of elements. This problem originates from the Rank Aggregation Problem for combining different linear ranks of elements. Later we define a probability measure based on dissimilarity between cyclic sequences based on the Kendall Tau distance. Next, we also introduce the problem of finding the cyclic sequence with minimum expected cost with respect to that probability measure. Finally, we establish certain relationships among some classical problems and the new problems that we have proposed.