Approximating the Maximum Weight of Linear Codes is APX-Complete(Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク

概要

• 論文の詳細を見る

• The minimum distance of a linear code C is a useful metric property for estimating the error correction upper bound of C and the maximum likelihood decoding of a linear code C is also of practical importance and of theoretical interest. These problems are known to be NP-hard to approximate within any constant relative error to the optimum. As a problem related to the above, we consider the maximization problem MAX-WEIGHT: Given a generator matrix of a linear code C, find a codeword c ⋳C with its weight as close to the maximum weight of C as possible. It is shown that MAX-WEIGHT¬ion;PTAS unless P=NP, however, no nontrivial approximation upper and lower bounds are known. In this paper, we investigate the complexity of MAX-WEIGHTto make the approximation upper and lower bounds more precise, adn show that (1) MAX-WEIGHTis APX-complete; (2) MAX-WEIGHTis approximable within relative error 1/2 to the optimum; (3) MAX-WEIGHTis not approximabler within relative error 1/10 to the optimum unless P=NP.

• 社団法人電子情報通信学会の論文
• 2000-04-25

著者

• Itoh Toshiya

  The Author Is With Global Scientific Information And Computing Center (gsic) Tokyo Institute Of Tech

• Itoh Toshiya

  The Author Is With Interdisciplinary Graduate School Of Science And Engineering Tokyo Institute Of T

関連論文

• A General Construction of Min-Wise Independent Permutations(Special Section on Discrete Mathematics and Its Applications)
• Constructing an Optimal Family of Min-Wise Independent Permutations
• Min-Wise Independence vs. 3-Wise Independence(Special Section on Discrete Mathematics and Its Applications)
• Approximating the Maximum Weight of Linear Codes is APX-Complete(Special Section on Discrete Mathematics and Its Applications)
• On Lower Bounds for the Communication Complexity of Private Information Retrieval : Special Section on Cryptography and Information Security

スポンサーリンク