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