Novel distance measures for rank aggregation

Rank aggregation is the problem of combining multiple candidate rankings into one list that best reflects the candidates' standing as a whole. Rank aggregation has many applications,in fields as diverse as bioinformatics, coding theory and social sciences.Mathematically, the rank aggregation problem can be formulated as finding a permutation thatrepresents the ``centroid'' of a set of permutations - i.e., a permutation that minimizes the averagedistance from the given set of permutations. The main issue arising in suchaggregation problems is to identify distance functions that are scalable, flexible and easy to compute.So far, no solutions that have these desirable properties were proposed.We introduce a new class of cost-constrained permutation metrics that can be approximated up to a constantin polynomial time. The cost functions are based on average transposition distances and forcosts that have a tree-metric form, the presented algorithms are exact. To prove the optimality of the distancecomputation procedure, we use Menger's theorem and graphical representations of permutations.We conclude the talk by describing a number of applications of the novel distance metric in ``collaborative rank aggregation'', coding for multilevel flash memories and reverse engineering genome reordering sequences.