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}&gt;d$. We call the additive approximation algorithm $A$ and find in polynomial time a feasible solution of value at most $\text{OPT}+d&lt;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$.