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?


2 Answers 2


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$.

  • $\begingroup$ In fact it looks like a general scheme for reducing a multiplicative approximation to an additive approximation. Good to keep that in mind. Thanks! $\endgroup$ Jan 8, 2019 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.