Theoretical Applications for Approximation Algorithms

Question

Lately I've started looking into approximation algorithms for NP-hard problems and I was wondering about the theoretical reasons for studying them. (The question is not meant to be inflammatory - I'm merely curious).

Some truly beautiful theory has come out of the study of approximation algorithms - the connection between the PCP theorem and hardness of approximation, the UGC conjecture, the Goeman-Williamson approximation algorithm, etc.

I was wondering though about the point of studying approximation algorithms for problems like Traveling Salesman, Asymmetric Traveling Salesman and other variants, various problems in mechanism design (for instance in combinatorial auctions), etc. Have such approximation algorithms been useful in other parts of theory in the past or are they studied purely for their own sake?

Note: I'm not asking about any practical applications since as far as I know, in the real world, it's mostly heuristics that are applied rather than approximation algorithms and the heuristics are rarely informed by any insight gained by studying the approximation algorithms for the problem.

Answer 1

I strongly disagree with the last paragraph. Blanket statements like that are not useful. If you look at papers in many systems areas such as networking, databases, AI and so on you will see that plenty of approximation algorithms are used in practice. There are some problems for which one desires very accurate answers; for example say an airline interesting in optimizing its fleet scheduling. In such cases people use various heuristics that take substantial computational time but get better results than a generic approximation algorithm can give.

Now for some theoretical reasons for studying approximation algorithms. First, what explains the fact that knapsack is very easy in practice while graph coloring is quite hard? Both are NP-Hard and poly-time reducible to each other. Second, by studying approximation algorithms for special cases of a problem one can pin-point what classes of instances are likely to be easy or hard. For example we know that many problems admit a PTAS in planar and minor-free graphs while they are much harder in arbitrary general graphs. The idea of approximation pervades modern algorithm design. For example, people use data streaming algorithms and without the approximation lens is hard to understand/design algorithms because even simple problems cannot be solved exactly.

Answer 2

Approximate counting is useful in complexity theory. For instance, Jin Cai uses it to show that $S_2^p \subseteq ZPP^{NP}$, see http://pages.cs.wisc.edu/~jyc/papers/S2-j.pdf

Answer 3

The best heuristics are really approximation algorithms. The most beautiful approximation algorithms are just "stupid" heuristics that work. For example, local search for clustering, greedy clustering (Gonzalez), one for the price of two, various greedy algorithms, etc, etc, etc.

So studying approximation algorithms is really about understanding what heuristics are guaranteed approximation algorithms. The hope is that research on approximation algorithms creates two kinds of cross-fertilization:

• Move ideas that work from heuristics into algorithms design tools. Similarly, move ideas from algorithm design into heuristics/algorithms that work well in practice.
• cross fertilization between a person that just graduated and a position.

In short, the world is not exact, inputs are not exact, target functions optimized by various algorithm problems are not exact and at best represent a fuzzy approximation to what one wants, and computations are not exact. Why would anybody learn exact algorithms? (Answer: Because exact algorithms are just really good approximation algorithms.)

In the real world, there are very few exact algorithms - you need to use approximation to be remotely relevant...

Answer 4

I also disagree with the "note", at least stated in this generality. Related to this, does anyone know if David Johnson's Kanellakis award talk is available somewhere?

Also, once we realize that all NP-hard problems are equivalent with respect to the worst-case complexity of exact solutions, it's very natural to inquire about the complexity of finding approximate solutions. And Chandra makes a great point about the change of perspective that approximation algorithms bring to algorithm design.

I am sure we should be able to come up with some interesting examples of approximation algorithms used to prove a theorem. For example, the $O(\log n)$ approximation to set cover can be used to show a better bound on the sample complexity of learning conjunctions.

Answer 5

Dealing with problems with continuous variables is very annoying with exact algorithms. For example, what does it mean to specify the edge-weights of a TSP instance with exact real numbers?

When we allow FPTAS algorithms for these problems, we can quantize these parameters to integers. This makes the problem much better behaved (can use standard Turing machines), but incurs a small error.