### Abstract

We address the problem of computing distances between permutations that take into account similarities between elements of the ground set dictated by a graph. The problem may be summarized as follows: Given two permutations and a positive cost function on transpositions that depends on the similarity of the elements involved, find a smallest cost sequence of transpositions that converts one permutation into another. Our focus is on costs that may be described via special metric-tree structures. The presented results include a linear-time algorithm for finding a minimum cost decomposition for simple cycles and a linear-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.

Original language | English (US) |
---|---|

Pages (from-to) | 157-175 |

Number of pages | 19 |

Journal | Discrete Applied Mathematics |

Volume | 232 |

DOIs | |

State | Published - Dec 11 2017 |

### Keywords

- Permutations
- Similarity distance
- Transposition distance

### ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Computing similarity distances between rankings'. Together they form a unique fingerprint.

## Cite this

*Discrete Applied Mathematics*,

*232*, 157-175. https://doi.org/10.1016/j.dam.2017.07.038