<p>You can think of $\epsilon$ as parametrizing a <em>family</em> of reductions to a <em>family</em> of approximation problems:</p>

<ul>
<li><p>The $\epsilon$-th problem is to compute a $1+\epsilon$ approximation to the underlying optimization problem.</p></li>
<li><p>The $\epsilon$-th reduction shows that the $\epsilon$-th problem is $\mathrm{NP}$-hard.</p></li>
</ul>

CC BY-SA 3.0
2016-07-15T21:13:46.217Z
2016-07-15T21:13:46.217Z
Andrew Morgan
<p>I have a reduction that proves that a problem is NP-hard to approximate to a factor $1 + \epsilon$ for any $0 &lt; \epsilon &lt; 1$. The reduction is polynomial in $n$ (the size of the instance of the problem I'm reducing from). However, the reduction also uses $1/\epsilon$. Since $\epsilon$ is a constant, this is considered a valid reduction.</p>

<p>What I'm concerned about is that as $\epsilon$ tends to zero, $1/\epsilon$ tends to infinity. How is my reduction a valid polynomial time reduction if it uses $1/\epsilon$ as part of the reduction construction when $1/\epsilon$ can tend to infinity. Most reductions have assumed this is valid since $1/\epsilon$ is a constant since $\epsilon$ is a constant. But I would like a more intuitive explanation of why this is still valid.</p>

<ds.algorithms><approximation-hardness><approximation>
Proving hardness of approximation with reduction in terms of 1/$\epsilon$
user1246462
# Proving hardness of approximation with reduction in terms of 1/$\epsilon$

(Asked by: username_0 on 2016-07-15)

I have a reduction that proves that a problem is NP-hard to approximate to a factor $1 + \epsilon$ for any $0 < \epsilon < 1$. The reduction is polynomial in $n$ (the size of the instance of the problem I'm reducing from). However, the reduction also uses $1/\epsilon$. Since $\epsilon$ is a constant, this is considered a valid reduction.

What I'm concerned about is that as $\epsilon$ tends to zero, $1/\epsilon$ tends to infinity. How is my reduction a valid polynomial time reduction if it uses $1/\epsilon$ as part of the reduction construction when $1/\epsilon$ can tend to infinity. Most reductions have assumed this is valid since $1/\epsilon$ is a constant since $\epsilon$ is a constant. But I would like a more intuitive explanation of why this is still valid.

**Tags:** ds.algorithms, approximation-hardness, approximation


---

## 1 answers

### Answer by username_1 on 2016-07-15. Score: 3 | Accepted answer

You can think of $\epsilon$ as parametrizing a *family* of reductions to a *family* of approximation problems:

* The $\epsilon$-th problem is to compute a $1+\epsilon$ approximation to the underlying optimization problem.
* The $\epsilon$-th reduction shows that the $\epsilon$-th problem is $\mathrm{NP}$-hard.


---

