I was watching a coursera video on Approximation algorithms and I understood the 2-approximation algorithm.
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.
- How does he skip from nobody found a 1.99-approximation algorithm
- Where does