<p>Unless <span class="math-container">$P=NP$</span>, there does not exist a polynomial time approximation algorithm that returns solutions of value at most <span class="math-container">$\text{OPT}+d$</span>.</p>

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

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

<p>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 <span class="math-container">$2$</span>. </p>

CC BY-SA 4.0
2019-01-08T11:16:09.370Z
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
CC BY-SA 4.0
2019-01-08T10:14:20.680Z
2019-01-08T10:14:20.680Z
Gamow
<p>Even if <span class="math-container">$d = d(n) \le n^{1-\epsilon}$</span> for an <span class="math-container">$m \times n$</span> matrix <span class="math-container">$A$</span>, no additive approximation <span class="math-container">$\mathrm{OPT} + d$</span> is possible unless <span class="math-container">$\mathsf{P} = \mathsf{NP}$</span>. Let <span class="math-container">$N = n^k$</span> for some constant <span class="math-container">$k$</span>, and take the Kronecker product <span class="math-container">$A' = I_{N} \otimes A$</span>, and <span class="math-container">$b' = e_{N} \otimes b$</span>, where <span class="math-container">$I_N$</span> is the <span class="math-container">$N\times N$</span> identity and <span class="math-container">$e_N$</span> is the <span class="math-container">$N\times 1$</span> all-ones vector. This is equivalent to just repeating the system of equations <span class="math-container">$N$</span> times with fresh variables each time. Then clearly the optimal solution to <span class="math-container">$A' x' = b'$</span> has <span class="math-container">$N\cdot\mathrm{OPT}$</span> nonzero entries. If you have a <span class="math-container">$d(Nn) \le n^{(1 -\epsilon)(k+1)}$</span> additive approximation for this problem, then at least one of the <span class="math-container">$N$</span> instances of the original system of equations has a solution with at most <span class="math-container">$\mathrm{OPT} + d(Nn)/N \le \mathrm{OPT} + n^{1-\epsilon(k+1)}$</span> nonzero entries. But <span class="math-container">$n^{1-\epsilon(k+1)} &lt; 1$</span> for a large enough <span class="math-container">$k$</span>, so one of your <span class="math-container">$N$</span> instances is solved optimally.</p>

<p>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. </p>

CC BY-SA 4.0
2019-01-09T20:24:24.783Z
2019-01-09T20:24:24.783Z
Sasho Nikolov
<p>In the problem <a href="https://en.wikipedia.org/wiki/Minimum_relevant_variables_in_linear_system" rel="nofollow noreferrer">Minimum Relevant Variables in Linear System</a> (Min-RVLS), the input is a linear system, e.g.:</p>

<p><span class="math-container">$$ A x = b $$</span></p>

<p>and the goal is to find a solution <span class="math-container">$x$</span> with as few nonzero variables as possible. </p>

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

<p>My question is: is anything known about <em>additive</em> approximations? In particular: what is the complexity of finding a solution that has at most <span class="math-container">$\text{OPT}+d$</span> nonzero variables, where <span class="math-container">$\text{OPT}$</span> is the smallest number of nonzero variables in a solution, and <span class="math-container">$d$</span> is some constant?</p>

<approximation-algorithms><optimization><linear-programming><approximation-hardness>
Minimum relevant variables in linear system - additive approximation
Erel Segal-Halevi
# Minimum relevant variables in linear system - additive approximation

(Asked by: username_0 on 2019-01-07)

In the problem [Minimum Relevant Variables in Linear System](https://en.wikipedia.org/wiki/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?

**Tags:** approximation-algorithms, optimization, linear-programming, approximation-hardness


---

## 2 answers

### Answer by username_1 on 2019-01-08. Score: 4 | Accepted answer

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

> **Comments:**
> **username_0**: In fact it looks like a general scheme for reducing a multiplicative approximation to an additive approximation. Good to keep that in mind. Thanks!  

---

### Answer by username_2 on 2019-01-09. Score: 1

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.


---

