-matrix
, integer
m
-vector
.
such that
Ax=b
.
for any
unless NP
QP [
9
].
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
[
9
].
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
[
203
].
Viggo Kann