Next: MAXIMUM SATISFYING LINEAR SUBSYSTEM
Up: Mathematical Programming
Previous: MINIMUM PLANAR RECORD PACKING
  Index
- INSTANCE:
Integer m x n-matrix
,
integer m-vector
.
- SOLUTION:
A rational n-vector
such that Ax=b.
- MEASURE:
The number of non-zero elements in x.
- Bad News:
Not in APX [16].
- Comment:
Not approximable within
for any
unless NP
QP [16].
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
[16].
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
[270].
- Garey and Johnson: MP5
Viggo Kann
1999-04-22