Title: On Approximating NP-Hard Optimization Problems

We discuss the efficient approximability of NP-hard optimization problems. Although the methods apply to several problems we concentrate on the problem of satisfying the maximal number of equations in an over-determined system of linear equations. We show that over the field of two elements it is NP-hard to approximate this problem within a factor smaller than 2. The result extends to any Abelian group with the size of group replacing the constant 2.

1991 Mathematics Subject Classification: 68Q25,68Q99

Keywords and Phrases: Approximation algorithms, NP-hard optimization problems, Linear equations

Full text: dvi.gz 21 k, dvi 47 k, ps.gz 75 k.

Home Page of DOCUMENTA MATHEMATICA