Computing similarity distances between rankings

Farzad Farnoud (Hassanzadeh), Olgica Milenkovic, Gregory J. Puleo, Lili Su

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)157-175
Number of pages19
JournalDiscrete Applied Mathematics
Volume232
DOIs
StatePublished - 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