The search functionality is under construction.
The search functionality is under construction.

Approximating the Maximum Weight of Linear Codes is APX-Complete

Toshiya ITOH

  • Full Text Views

    0

  • Cite this

Summary :

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 PTAS unless P=NP, however, no nontrivial approximation upper and lower bounds are known. In this paper, we investigate the complexity of MAX-WEIGHT to make the approximation upper and lower bounds more precise, and show that (1) MAX-WEIGHT is APX-complete; (2) MAX-WEIGHT is approximable within relative error 1/2 to the optimum; (3) MAX-WEIGHT is not approximable within relative error 1/10 to the optimum unless P=NP.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.4 pp.606-613
Publication Date
2000/04/25
Publicized
Online ISSN
DOI
Type of Manuscript
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category

Authors

Keyword