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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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