Next: MAXIMUM SATISFYING LINEAR SUBSYSTEM Up: Mathematical Programming Previous: MINIMUM PLANAR RECORD PACKING Index

### MINIMUM RELEVANT VARIABLES IN LINEAR SYSTEM

- 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 NPQP [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