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?
Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Recently improved to $\sqrt 2$. $\endgroup$
    – Yuval Filmus
    Commented 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$
    – heretoinfinity
    Commented Apr 10, 2021 at 13:06
  • $\begingroup$ Right. The truth is probably 2. $\endgroup$
    – Yuval Filmus
    Commented 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$
    – heretoinfinity
    Commented 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$
    – Yuval Filmus
    Commented Apr 10, 2021 at 13:38

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ So it could be possible to go lower than 1.3606? $\endgroup$
    – heretoinfinity
    Commented 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
    Commented 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
    Commented Apr 9, 2021 at 18:40
  • 2
    $\begingroup$ A recent result improves the hardness of approximation to $\sqrt 2$. $\endgroup$
    – Yuval Filmus
    Commented 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
    Commented Apr 9, 2021 at 22:37

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.