2
$\begingroup$

I was watching a coursera video on Approximation algorithms and I understood the 2-approximation algorithm.

slide

Later, the professor asks if we can do any better. The lecturer went on to say that computing 1.3606 approximation is NP-hard in the following words at 8:14.

Here's the transcript for that part.

Actually, what is also interesting to note is that okay, maybe we still have some hope that we can get a little bit below two for the approximation ratio, but as the second staple that you see here shows is that it's not possible to get really close to one, but it's impossible to get something better than roughly 1.3, because already computing a 1.36 approximation as you see here, already that problem is NP-hard.

  1. How does he skip from nobody found a 1.99-approximation algorithm to getting 1.3606 is NP-Hard?
  2. Where does 1.3606 come from?
$\endgroup$
5
  • 1
    $\begingroup$ Recently improved to $\sqrt 2$. $\endgroup$ Apr 9, 2021 at 22:21
  • $\begingroup$ Meaning that it has been shown that it is NP-hard to find a $\sqrt{2}$ approximation ratio? $\endgroup$ Apr 10, 2021 at 13:06
  • $\begingroup$ Right. The truth is probably 2. $\endgroup$ Apr 10, 2021 at 13:21
  • $\begingroup$ A bit confused now that you have written $2$ and not $\sqrt{2}$. You mean that it is more likely that we can't beat $2$ as the approximation ratio? $\endgroup$ Apr 10, 2021 at 13:36
  • $\begingroup$ It’s known that you can’t do better than $\sqrt 2$, and it’s conjectured that you can’t do better than 2. $\endgroup$ Apr 10, 2021 at 13:38

1 Answer 1

4
$\begingroup$

The fact that nobody found a $1.99$ approximation doesn't necessarily mean that the problem of finding one is $\mathsf{NP}$-hard (e.g., it might be the case that that $\mathsf{P} \neq \mathsf{NP}$ and a polynomial-time $1.99$-approximation algorithm exists, we are just unaware of it).

Additionally, we can prove that finding a $1.3606$-approximation is a $\mathsf{NP}$-hard problem, i.e., if $\mathsf{P} \neq \mathsf{NP}$ no $1.3606$-approximation algorithm exists. This is not a direct consequence of the previous fact, but a separate result by Irit Dinur and Samuel Safra. The details can be found here.

$\endgroup$
6
  • $\begingroup$ So it could be possible to go lower than 1.3606? $\endgroup$ Apr 9, 2021 at 17:54
  • 1
    $\begingroup$ From what we know, we cannot rule out the existence of a polynomial-time $x$-approximation algorithm with $x<1.3606$. However that would imply $\mathsf{P}=\mathsf{NP}$. $\endgroup$
    – Steven
    Apr 9, 2021 at 17:56
  • 2
    $\begingroup$ It could be useful depending on the time complexity of said algorithm. for example if we don't know a better exact algorithm than in $\Omega(n^{100})$, but know a $1.3$-approximation algorithm in $O(n^2)$. $\endgroup$
    – Nathaniel
    Apr 9, 2021 at 18:40
  • 2
    $\begingroup$ A recent result improves the hardness of approximation to $\sqrt 2$. $\endgroup$ Apr 9, 2021 at 22:22
  • 1
    $\begingroup$ @YuvalFilmus, thanks for pointing this out! Here is the relevant paper (see, in particular, the discussion of page 6). $\endgroup$
    – Steven
    Apr 9, 2021 at 22:37

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.