10. Parametric Pruning

As mentioned in Section 8.2, the difficult part of solving an NP-hard problem is finding the optimal objective function value. When solving a minimization problem, parametric pruning starts by determining a good lower bound on the objective function value, essentially by guessing: It tries larger and larger objective function values until it can no longer guarantee that a solution with the current objective function value does not exist. It then discards all parts of the input that are not part of a solution of this objective function value, solves a related but simpler problem on the pruned input, and uses the solution to this simpler problem to construct a solution to the original problem that is within a certain factor of the lower bound determined in the guessing step. This will become clearer using an example. We illustrate this technique using two variants of the metric \(k\)-center problem:

• In Section 10.1, we consider the metric \(k\)-center problem, where the goal is to choose a subset of \(k\) vertices, "centers", in a graph so that the maximum distance from any vertex in the graph to its closest center is minimized. We will use the parametric pruning technique to obtain a \(2\)-approximation for this problem.

• In Section 10.2, we prove that this \(2\)-approximation is the best possible, that is, that there is no algorithm for the metric \(k\)-center problem that achieves an approximation ratio better than \(2\) unless \(\textrm{P} = \textrm{NP}\). Note that this is stronger than simply providing a family of tight inputs for the algorithm in Section 10.1. It shows that no other algorithm can beat the approximation ratio achieved by this algorithm.

• In Section 10.3, we consider a generalization of the metric \(k\)-center problem where the vertices have associated costs. In this version of the problem, we aren't given a number of centers to pick. Instead, we are given a budget \(B\) and we are asked to pick a set of centers of total cost not exceeding \(B\). Again, the goal is to minimize the maximum distance of any vertex to its closest center. Using parametric pruning again, we obtain a \(3\)-approximation for this problem.