TY - GEN
T1 - On the minimum weight problem of permutation codes under chebyshev distance
AU - Shieh, Min-Zheng
AU - Tsai, Shi-Chun
PY - 2010/8/23
Y1 - 2010/8/23
N2 - 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 ℓ∞-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 - ε for any ε > 0.
AB - 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 ℓ∞-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 - ε for any ε > 0.
UR - http://www.scopus.com/inward/record.url?scp=77955691502&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2010.5513663
DO - 10.1109/ISIT.2010.5513663
M3 - Conference contribution
AN - SCOPUS:77955691502
SN - 9781424469604
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 1183
EP - 1187
BT - 2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings
T2 - 2010 IEEE International Symposium on Information Theory, ISIT 2010
Y2 - 13 June 2010 through 18 June 2010
ER -