Comment:
Not approximable within
for any
unless NPQP [17].
The above nonapproximability results are still true for the
variation in which the solutions are restricted by
instead of
Ax=b.
Variation in which the solution vector is restricted to contain binary
numbers is NPO PB-complete and is not approximable within
for any
[17].
The complementary maximization problem, where the number of zero elements
in the solution is to be maximized, and the solution vector is restricted
to contain binary numbers, is NPO PB-complete and is not approximable within
for any
[285].