  Codes over permutations under the infinity norm have been recently suggested
as a coding scheme for correcting limited-magnitude errors in the rank
modulation scheme. Given such a code, we show that a simple relabeling
operation, which produces an isomorphic code, may drastically change the
minimal distance of the code. Thus, we may choose a code structure for
efficient encoding/decoding procedures, and then optimize the code's minimal
distance via relabeling.
  We formally define the relabeling problem, and show that all codes may be
relabeled to get a minimal distance at most 2. The decision problem of whether
a code may be relabeled to distance 1 is shown to be NP-complete, and
calculating the best achievable minimal distance after relabeling is proved
hard to approximate.
  Finally, we consider general bounds on the relabeling problem. We
specifically show the optimal relabeling distance of cyclic groups. A specific
case of a general probabilistic argument is used to show $\agl(p)$ may be
relabeled to a minimal distance of $p-O(\sqrt{p\ln p})$.
