Comparing Euclidean, Kendall tau metrics toward extending LP decoding

摘要

In recent years permutation codes have emerged as a field of great interest with new applications being suggested. In this paper we investigate two distance metrics and their induced weight functions on subgroups of the symmetric group, Sn, of permutations on n elements. Specifically, we introduce the Euclidean weight and compare its weight distribution to that of the Kendall tau weight. Our primary contribution is to extend LP (linear programming) decoding methods invented for permutation codes endowed with a Euclidean distance metric to codes utilizing the Kendall tau distance metric.