8.2. Approximation Algorithms

Since we should not expect to solve any NP-hard optimization problem optimally in polynomial time, a natural question we may ask is whether we can obtain a suboptimal but good solution in polynomial time.

Heuristics are one way to try to find good solutions efficiently, and they can be extremely effective in practice. A downside of heuristics is that they do not provide any guarantees: They may produce very good solutions in practice, but we cannot prove that they always provide good solutions; or they may always produce very good solutions and do so quickly in practice, but we cannot prove that the algorithms are guaranteed to be fast.

We do not discuss heuristics further in these notes and instead focus on (polynomial-time) approximation algorithms. In contrast to heuristics, these are algorithms for which we can prove that they are fast, that they always run in polynomial time, and we are able to provide a provable bound on how much worse than an optimal solution the computed solution may be.

Let us formalize this notion of "bounding how bad the computed solution can be":

A \(\boldsymbol{c}\)-approximation algorithm for some minimization problem \(P\) with objective function \(f\) is an algorithm which, for any instance \(I\) of \(P\), computes a solution \(S\) whose objective function value \(f(S)\) is at most \(c \cdot \textrm{OPT}(I)\), where \(\textrm{OPT}(I)\) denotes the objective function value of an optimal solution of \(P\) on the input \(I\).

The factor \(c\) is called the approximation ratio achieved by the algorithm.

If \(P\) is a maximization problem, then a \(c\)-approximation algorithm for \(P\) computes a solution \(S\) for any instance \(I\) of \(P\) whose objective function value is \(f(S) \ge c \cdot \textrm{OPT}(I)\).

In the case of the vertex cover problem, this means that for any input graph \(G\), a \(c\)-approximation algorithm is guaranteed to compute a vertex cover that is at most \(c\) times bigger than a minimum vertex cover of \(G\).

Finding the Optimal Objective Function Value is the Hard Part

It is not hard to prove that the hard part of solving an NP-hard optimization problem \(P\) is finding \(\textrm{OPT}(I)\) for any instance \(I\) of \(P\): Assume we are given some polynomial-time algorithm \(\mathcal{A}\) which, given an instance \(I\) of \(P\) and some threshold \(t\), decides whether \(\textrm{OPT}(I) \le t\). This algorithm doesn't even compute \(\textrm{OPT}(I)\): It only decides whether \(\textrm{OPT}(I) \le t\). Given such an algorithm \(\mathcal{A}\), we can use it to design a polynomial-time algorithm that finds an optimal solution of \(P\) on the input \(I\). Since \(P\) is NP-hard, we believe that there is no polynomial-time algorithm that finds an optimal solution for any given instance of \(P\). Thus, a polynomial-time algorithm \(\mathcal{A}\) that decides whether \(\textrm{OPT}(I) \le t\) is also unlikely to exist.

This is a major problem for designing approximation algorithms: In order to prove a bound on the approximation ratio of a given algorithm, we need to compare the objective function value of the computed solution with the optimal objective function value, but computing the optimal objective function value is NP-hard. How do we bound the approximation ratio then? The answer is, we need to find a good lower bound (for minimization problems) or upper bound (for maximization problems) on \(\textrm{OPT}(I)\).

For the vertex cover problem, we need to establish a lower bound \(\ell\) on the size of any vertex cover of the input graph \(G\). In particular, \(\textrm{OPT}(G) \ge \ell\). If we can argue that our algorithm computes a vertex cover of size at most \(c\cdot\ell\), then this vertex cover also has size at most \(c\cdot\textrm{OPT}(G)\), that is, the algorithm is a \(c\)-approximation algorithm.

What is a good lower bound on the size of any vertex cover of some graph \(G\)? Consider a maximal matching \(M\) of \(G\). See Figure 8.2. Since no two edges in \(M\) share an endpoint, no vertex of \(G\) covers more than one edge in \(M\), that is, we need at least \(|M|\) vertices to cover the edges in \(M\). Thus, any vertex cover of \(G\) has size at least \(|M|\).

Figure 8.2: Coming soon!

Now consider the set \(C_M = \{ u, v \mid (u,v) \in M \}\). Clearly, \(|C_M| = 2|M|\). Moreover, it is a vertex cover of \(G\). Indeed, if there exists an edge \((u,v)\) not covered by \(C_M\), then \(u,v \notin C_M\), that is, the edge \((u,v)\) does not share any endpoint with any edge in \(M\). Thus, \(M \cup \{(u,v)\}\) is a matching, a contradiction because \(M\) is a maximal matching.

This gives a simple linear-time \(2\)-approximation algorithm for the vertex cover problem: Compute a maximal matching of \(G\) and return the set of all matched vertices.

Theorem 8.1: There exists a linear-time \(2\)-approximation algorithm for the vertex cover problem.

Inapproximability and Families of Tight Inputs

Given any algorithm, we should always ask ourselves whether it can be improved. In the case of approximation algorithms, the central question is whether the approximation guarantee can be improved. This question has to be asked carefully, in order to obtain a meaningful answer. For example, the answer is always yes if we place no bound on the running time of the better algorithm we hope to obtain: If the optimal is computable, we can always obtain an optimal solution given enough time. The right way to ask this question is whether there exists a polynomial-time algorithm that provides a better approximation guarantee. If the problem is NP-hard, no polynomial-time algorithm that solves the problem exactly exists unless \(\textrm{P}=\textrm{NP}\).

For some problems, we are able to prove that they cannot be approximated below a certain threshold unless \(\textrm{P}=\textrm{NP}\). For example, we will show that, assuming that \(\textrm{P} \ne \textrm{NP}\), \(2\) is essentially the best approximation guarantee for the \(k\)-center problem that can be obtained in polynomial time. The way to prove this is to show that an algorithm with approximation ratio \(c\) sufficiently smaller than \(2\) can be used to solve some NP-hard decision problem. Since the latter is not possible in polynomial time unless \(\textrm{P} = \textrm{NP}\), no polynomial-time algorithm with approximation factor \(c\) exists, again unless \(\textrm{P} = \textrm{NP}\).

For other problems, we are able to prove that they can be approximated arbitrarily well. The bin packing problem and the travelling salesman problem are two such problems. They can be approximated, in polynomial time, to within a factor of \(1 + \epsilon\) of an optimal solution, for any constant \(\epsilon > 0\). Such a solution is called a polynomial-time approximation scheme (PTAS). There is, however, a price that needs to be paid for improved approximation guarantees: The running time of the algorithm increases as \(\epsilon\) decreases. This should not be surprising because, as \(\epsilon\) approaches \(0\), the running time should approach exponential time, given that we are trying to solve an NP-hard optimization problem. Since the running time of the algorithm depends on \(\epsilon\), we should ask how bad the dependence of the running time on \(\epsilon\) is. If the dependence is polynomial in \(\frac{1}{\epsilon}\), we call the PTAS a fully polynomial-time approximation scheme (FPTAS). A PTAS that is not an FPTAS can have an exponential or worse dependence on \(\frac{1}{\epsilon}\); it only has to be possible to compute a \((1 + \epsilon)\)-approximation in polynomial time for any fixed \(\epsilon > 0\).

Both inapproximability results, such as the inapproximability result for the \(k\)-center problem mentioned above, and (F)PTASs require some care to obtain. A more immediate question we can ask about a given approximation algorithm, which is usually much easier to answer, is whether its analysis can be improved. Thus, we are not asking whether there is a better algorithm, only whether we could possibly prove that the algorithm we have already developed does in fact achieve a better approximation ratio than we have proven so far. Since every approximation algorithm is based on some lower or upper bound on the optimal objective function value \(\textrm{OPT}\), the approximation ratio the algorithm is able to guarantee depends on the quality of this lower or upper bound. Thus, we may ask whether there exists a family of tight inputs, an infinite family of inputs for which the algorithm cannot perform significantly better than the bound we proved.¹

As an example, consider the matching-based approximation algorithm for the vertex cover problem. A family of tight inputs is provided by the set of complete bipartite graphs \(K_{n,n}\) on \(2n\) vertices. See Figure 8.3.

Figure 8.3: Coming soon!

Any maximal matching of \(K_{n,n}\) includes \(n\) edges and thus matches all \(2n\) vertices of the graph. The approximation algorithm thus includes all \(2n\) vertices in the vertex cover. However, a vertex cover of size \(n\) exists: the \(n\) vertices in one of the two bipartitions cover all edges. Thus, the vertex cover the algorithm computes for \(K_{n,n}\) is by a factor \(2\) larger than an optimal vertex cover; there exist an infinite number of inputs for which the algorithm does not achieve an approximation guarantee better than \(2\).

Summary

To summarize, the first approach to solving NP-hard optimization problems we consider is to compute good approximations of optimal solutions in polynomial time.

• The proof that these algorithms output a \(c\)-approximation of an optimal solution for every possible input and some fixed factor \(c\) requires us to come up with a lower bound or upper bound on the objective function value of an optimal solution to which we can compare the solution computed by the algorithm. We cannot compute the optimal objective function value, as this is the hard core of the problem.

• We may ask whether the approximation ratio achieved by an algorithm is the best possible. Such a result is called an inapproximability result, a proof that there is no polynomial-time algorithm that achieves an approximation ratio better than a certain threshold unless \(\textrm{P} = \textrm{NP}\).

• The simpler question is whether our analysis of a given algorithm is tight, whether we can prove that there are inputs where the solution output by the algorithm is exactly as bad as predicted by our analysis.

• Finally, there are problems that can be approximated arbitrarily well, to within an approximation ratio of \(1 + \epsilon\) for an arbitrary constant \(\epsilon > 0\). Such algorithms are called polynomial-time approximation schemes. We will not discuss these in detail in this course, even though they are often based on really beautiful ideas. You may for example have a look at the PTAS for the metric travelling salesman problem by Sanjeev Arora. One excuse for not covering PTASs in this course, apart from having only limited time and having to choose judiciously which problems and techniques to cover, is that in spite of their beauty, PTASs are often impractical. They often use fairly complex algorithmic building blocks and, once we choose very small values of \(\epsilon\) to benefit from the PTAS's ability to provide very tight approximations of optimal solutions, they are often slower in practice than carefully implemented exponential-time algorithms for the same problem, which actually produce optimal solutions.