On the minimum weight problem of permutation codes under Chebyshev distance

Abstract

Permutation codes of length $n$ and distance $d$ is a set of permutations on $n$ symbols, where the distance between any two elements in the set is at least $d$. Subgroup permutation codes are permutation codes with the property that the elements are closed under the operation of composition. In this paper, under the distance metric ${\ell }_{\infty }$-norm, we prove that finding the minimum weight codeword for subgroup permutation code is NP-complete. Moreover, we show that it is NP-hard to approximate the minimum weight within the factor $7/6-\epsilon$ for any $\epsilon >0$.

5 pages. ISIT 2010

References in corpus (1)

• Correcting Limited-Magnitude Errors in the Rank-Modulation Scheme