# Minimum relevant variables in linear system - additive approximation

In the problem Minimum Relevant Variables in Linear System (Min-RVLS), the input is a linear system, e.g.:

$$A x = b$$

and the goal is to find a solution $$x$$ with as few nonzero variables as possible.

The problem is known to be NP-hard and hard to approximate to within a constant multiplicative factor (see the wikipedia page for details).

My question is: is anything known about additive approximations? In particular: what is the complexity of finding a solution that has at most $$\text{OPT}+d$$ nonzero variables, where $$\text{OPT}$$ is the smallest number of nonzero variables in a solution, and $$d$$ is some constant?

Unless $$P=NP$$, there does not exist a polynomial time approximation algorithm that returns solutions of value at most $$\text{OPT}+d$$.

Suppose otherwise, and consider some fixed $$d$$ for which there does exist such an approximation algorithm $$A$$. We construct a new multiplicative polynomial time approximation algorithm from $$A$$, that always returns solutions of value at most $$2\cdot\text{OPT}$$. Hence consider an arbitrary instance $$I$$ of Min-RVLS:

• For all $$k=1,\ldots,d$$ check whether $$I$$ has a solution $$x$$ with $$k$$ nonzero variables. This can be done by checking every subset $$S$$ of $$k$$ Variables: Set all variables outside $$S$$ to zero, and solve the linear equation system for the remaining variables. Since there are only $$O(n^d)$$ subsets to be checked, the overall running time is polynomial. (Here we use that $$d$$ is a fixed integer.)
• If the first step does not reveal any feasible solution, we know that $$\text{OPT}>d$$. We call the additive approximation algorithm $$A$$ and find in polynomial time a feasible solution of value at most $$\text{OPT}+d<2\cdot\text{OPT}$$.

As we either detect an optimal solution (first step) or a solutions with value at most twice the optimum (second step), the resulting polynomial time approximation algorithm has a multiplicative approximation guarantee of $$2$$.

• In fact it looks like a general scheme for reducing a multiplicative approximation to an additive approximation. Good to keep that in mind. Thanks! – Erel Segal-Halevi Jan 8 '19 at 11:16

Even if $$d = d(n) \le n^{1-\epsilon}$$ for an $$m \times n$$ matrix $$A$$, no additive approximation $$\mathrm{OPT} + d$$ is possible unless $$\mathsf{P} = \mathsf{NP}$$. Let $$N = n^k$$ for some constant $$k$$, and take the Kronecker product $$A' = I_{N} \otimes A$$, and $$b' = e_{N} \otimes b$$, where $$I_N$$ is the $$N\times N$$ identity and $$e_N$$ is the $$N\times 1$$ all-ones vector. This is equivalent to just repeating the system of equations $$N$$ times with fresh variables each time. Then clearly the optimal solution to $$A' x' = b'$$ has $$N\cdot\mathrm{OPT}$$ nonzero entries. If you have a $$d(Nn) \le n^{(1 -\epsilon)(k+1)}$$ additive approximation for this problem, then at least one of the $$N$$ instances of the original system of equations has a solution with at most $$\mathrm{OPT} + d(Nn)/N \le \mathrm{OPT} + n^{1-\epsilon(k+1)}$$ nonzero entries. But $$n^{1-\epsilon(k+1)} < 1$$ for a large enough $$k$$, so one of your $$N$$ instances is solved optimally.

This is quite common, BTW: most optimization problems allow some kind of "amplification" like this, which usually implies no non-trivial additive approximation is possible.