  We address the problem of computing distances between rankings that take into
account similarities between candidates. The need for evaluating such distances
is governed by applications as diverse as rank aggregation, bioinformatics,
social sciences and data storage. The problem may be summarized as follows:
Given two rankings and a positive cost function on transpositions that depends
on the similarity of the candidates involved, find a smallest cost sequence of
transpositions that converts one ranking into another. Our focus is on costs
that may be described via special metric-tree structures and on complete
rankings modeled as permutations. The presented results include a
quadratic-time algorithm for finding a minimum cost decomposition for simple
cycles, and a quadratic-time, $4/3$-approximation algorithm for permutations
that contain multiple cycles. The proposed methods rely on investigating a
newly introduced balancing property of cycles embedded in trees, cycle-merging
methods, and shortest path optimization techniques.
