Simple problem whose approximation ratio is still open.

Question

I am preparing for a talk on "Approximation Algorithms", aimed at undergraduate students. In order to motivate the topic, I want to give them an example of a problem which is easy to describe and has a ridiculously easy approximation algorithm. But the question - "Whether one can one can do better?" must be still open for that problem.

In short, what is a simple-to-describe problem whose approximation ratio is still open?

EDIT: Finding minimum Vertex Cover of a simple graph $G(V,E)$ happens to have a simple algorithm with approximation ratio 2. But its approximation ratio is still an open question.

Answer 1

I'd recommend approximation of functions by polynomials. Motivation is easy -- this is how computer libraries calculate trigonometric (and other) functions. Or, they used to, at least. Explanations are easy because you can draw graphs of approximations and error functions.

The obvious algorithm is Taylor expansion. This is very good near one single point and bad elsewhere, so it's fairly useless. Plot the error function.

Then try interpolation, to try to get the error function to be more "flat". How should the interpolation points be distributed? Talk about the Runge phenomenon.

End up with Chebyshev approximations and Remez algorithm. If you have access to Matlab, get the Chebfun package to play with.

For a related problem that is open (as far as I know), use approximation of 2D curves by polynomials. See this question and this one.

The second question has a good answer for circles, but it doesn't look like it generalises easily to other planar curves.

Answer 2

I think there are two canonical and very prominent examples.

• Metric TSP: This problem has an easy 2-approximation, and you can also teach Christophides algorithm, which has the current best approximation factor (3/2), which is not that difficult to grasp for undergrads. As an addition you can tell that it is known that there is no (polynomial) approximation algorithm with a better ratio than 185/184 unless ${\sf P}={\sf NP}$ (Lampis, 2012). Also it is interesting that there is a conjecture that there exists a 4/3 approximation (Held-Karp relaxiation) but nobody was able to prove this one yet.

• Vertex Cover: Vertex cover has a 2-approximation. Actually there are two easy algorithms giving a 2-approximation: (i) Rounding a relaxed LP formulation, and (ii) a combinatorial algorithm using the Layering technique. Find out about the inapproximability results by yourself.

You can find more open problems in the book "Approximation Algorithms" by Vazirani (great book!). It contains the VC algorithms I mentioned above. Check out Section 30.