The search functionality is under construction.

The search functionality is under construction.

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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Toshiya ITOH, "Approximating the Maximum Weight of Linear Codes is APX-Complete" in IEICE TRANSACTIONS on Fundamentals,
vol. E83-A, no. 4, pp. 606-613, April 2000, doi: .

Abstract: 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*.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_4_606/_p

Copy

@ARTICLE{e83-a_4_606,

author={Toshiya ITOH, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Approximating the Maximum Weight of Linear Codes is APX-Complete},

year={2000},

volume={E83-A},

number={4},

pages={606-613},

abstract={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*.

keywords={},

doi={},

ISSN={},

month={April},}

Copy

TY - JOUR

TI - Approximating the Maximum Weight of Linear Codes is APX-Complete

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 606

EP - 613

AU - Toshiya ITOH

PY - 2000

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E83-A

IS - 4

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - April 2000

AB - 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*.

ER -