Transformation from MINIMUM WEIGHTED SATISFIABILITY.
Variation in which there are at most 3 non-zero entries on each
row of the matrix is still NPO-complete [Klauck, --], but if
there are at most 2 non-zero entries on each row it
is approximable within 2 .
If all entries of A are non-negative, and there are
at most k non-zero entries on each row with k constant,
the problem is approximable within k .
Variation in which
for all i is NPO PB-complete and
not approximable within