On approximating NP-hard optimization problems
Consider the problem of satisfying the maximal number of equations in an over-determined system of linear equations. The author shows that it is NP-hard to approximate this problem within a factor smaller than 2.
scientific article; zbMATH DE number 1184382