TY - JOUR

T1 - Computing similarity distances between rankings

AU - Farnoud (Hassanzadeh), Farzad

AU - Milenkovic, Olgica

AU - Puleo, Gregory J.

AU - Su, Lili

N1 - Publisher Copyright:
© 2017 Elsevier B.V.

PY - 2017/12/11

Y1 - 2017/12/11

N2 - 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.

AB - 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.

KW - Permutations

KW - Similarity distance

KW - Transposition distance

UR - http://www.scopus.com/inward/record.url?scp=85029511722&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85029511722&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2017.07.038

DO - 10.1016/j.dam.2017.07.038

M3 - Article

AN - SCOPUS:85029511722

SN - 0166-218X

VL - 232

SP - 157

EP - 175

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -