MINIMUM RELEVANT VARIABLES IN LINEAR SYSTEM

• INSTANCE: Integer $m\times n$-matrix $A\in Z^{m\cdot n}$, integer m-vector $b\in Z^m$.

• SOLUTION: A rational n-vector $x\in Q^n$ such that Ax=b.

• MEASURE: The number of non-zero elements in x.

  
  

• Bad News: Not in APX [17].

• Comment: Not approximable within $2^{\log^{1-\varepsilon } n}$ for any $\varepsilon >0$ unless NP$\subset$QP [17]. The above nonapproximability results are still true for the variation in which the solutions are restricted by $Ax\ge b$ 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 $n^{0.5-\varepsilon }$ for any $\varepsilon >0$ [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 $(n+m)^{1/3-\varepsilon }$ for any $\varepsilon >0$ [285].

• Garey and Johnson: MP5