Introduction to Approximation Algorithms

For many important optimization problems, there is no known polynomial-time algorithm to compute the exact optimum. In fact, the great many NP-complete problems problems are hard to solve, in the sense that the existence of a polynomial-time algorithm for solving any one of them would imply polynomial-time algorithms for all the rest.

The study of approximation algorithms arose as a way to circumvent the apparent hardness of these problems by relaxing the algorithm designer's goal: instead of trying to compute an exactly optimal solution, we aim to compute a solution whose value is as close as possible to that of the optimal solution. However, in some situations it is desirable to run an approximation algorithm even when there exists a polynomial-time algorithm for computing an exactly optimal solution. For example, the approximation algorithm may have the benefit of faster running time, a lower space requirement, or it may lend itself more easily to a parallel or distributed implementation.

These considerations become especially important when computing on “big data,” where the input size is so astronomical that a running time which is a high-degree polynomial of the input size (or even quadratic, for that matter) cannot really be considered an efficient algorithm, at least on present-day hardware.

To make the definition of approximation algorithms precise, we say that an algorithm ALG for a maximization problem is an $\alpha$-approximation algorithm (or that its approximation factor is $\alpha$) if the following inequality holds for every input instance $x$:

$$ALG(x) \leq OPT(x) \leq \alpha · ALG(x).$$

Here $OPT(x)$ denotes the value of the problem's objective function when evaluated on the optimal solution to input instance $x$, and $ALG(x)$ denotes the algorithm's output when it runs on input instance $x$. Note that the definition only requires the algorithm to output a number (approximating the value of the optimal solution) and not the approximate solution itself. In most cases, it is possible to design the algorithm so that it also outputs a solution attaining the value $ALG(x)$, but in these notes we adopt a definition of approximation algorithm that does not require the algorithm to do so.

Similarly, for a minimization problem, an $\alpha$-approximation algorithm must satisfy:

$$OPT(x) \leq ALG(x) \leq \alpha· OPT(x).$$

Note that in both cases the approximation factor $\alpha$ is a number greater than or equal to 1.