ECCC - TR00-091

ECCC

Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login

Register

Classic Style

REPORTS > DETAIL:

Paper:

TR00-091 | 21st December 2000 00:00

Approximability of Dense Instances of NEAREST CODEWORD Problem

Contact

Add Comment

TR00-091 Authors: Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski
Publication: 21st December 2000 16:25
Downloads: 2555

Keywords:

Approximation Algorithms, Dense Instances, Linear Equations, lower bounds, nearest codeword problem, Polynomial Time Approximation Schemes

Abstract:

We give a polynomial time approximation scheme (PTAS) for dense
instances of the NEAREST CODEWORD problem.

ISSN 1433-8092 | Imprint