11. Dual Fitting

Let me say it again: The key to obtaining a good approximation algorithm for an NP-hard minimization problem is to find a good lower bound on the objective function value of an optimal solution. This should sound familiar: For linear programming, we proved that a solution to a linear program is optimal if we can find a feasible solution of the dual linear program with the same objective function value. For the maximum flow problem, we showed that a maximum flow corresponds to a minimum cut and, in fact, this result can also be expressed rather elegantly as a pair of linear programs.

When considering NP-hard optimization problems that can be expressed as integer linear programs, we cannot hope in general that there exists a solution to this ILP that matches the objective function value of the dual: This equality holds only for fractional linear programs. However, the objective function value of any feasible solution of the dual is still a lower bound on the objective function value of an optimal solution of the ILP because it is a lower bound on the objective function value of an optimal solution of the LP relaxation. Thus, if we can find a feasible solution of the primal ILP and a feasible solution of the dual LP whose objective function values differ by at most \(c\), then the feasible solution of the ILP must be a \(c\)-approximation of an optimal solution of the ILP.

This idea of finding such a pair of feasible primal and dual solutions is central to the theory of approximation algorithms, and we will explore the use of linear programming and LP duality in approximation algorithms in the next three chapters. Even purely combinatorial approximation algorithms are often best understood using the language of LP duality. To demonstrate this, we discuss the technique of dual fitting in this chapter. This technique does not use linear programming in the algorithm at all, nor as a tool to guide the design of the algorithm: Linear programming is used only in the analysis of the algorithm. The idea is to construct a feasible dual solution whose objective function value is by at most a certain factor \(c\) smaller than the objective function value of the solution computed by the algorithm to be analyzed. We are trying to "fit" a large dual solution below the primal solution comptued by the algorithm. This proves that the algorithm computes a \(c\)-approximation of an optimal solution.

In the next chapter, we show how to use the primal-dual schema to obtain approximation algorithms for NP-hard optimization problems. You should recall from the discussion of preflow-push algorithms to compute maximum flows, of the successive shortest paths algorithm to compute minimum-cost flows, and of the Hungarian algorithm to compute a minimum-weight perfect matching that algorithms based on the primal-dual schema are purely combinatorial algorithms: They do not use a general-purpose LP solver, such as the Simplex Algorithm, to find optimal solutions to the primal and dual LPs. Where LP duality is used in the design of primal-dual algorithms is in guiding the design of the algorithm. The same is true for approximation algorithms based on the primal-dual schema. The correctness of preflow-push algorithms, of the successive shortest paths algorithm, and of the Hungarian algorithm depends on complementary slackness. All of these algorithms maintain the invariant that the current, possibly infeasible, primal solution and the current feasible dual solution satisfy complementary slackness. Again, we cannot do this for NP-hard problems expressed as ILPs because in general, there is no feasible integral primal solution whose objective function value matches that of an optimal dual solution. Therefore, approximation algorithms based on the primal-dual schema use a relaxation of complementary slackness that guarantees that the objective function values of the primal and dual solutions differ by at most a certain factor.

The final application of linear programming to approximately solve NP-hard problems, discussed in Chapter 13, does use linear programming in the algorithm itself. The general idea is to solve the relaxation of the ILP formulation of the problem optimally, using some general-purpose algorithm for solving linear programs, such as the Simplex Algorithm.¹ This produces a fractional solution of the problem. Then we round these fractional values so that the resulting integral solution remains feasible and its cost, compared to the optimal fractional solution, is not increased too much. Quite naturally, this technique is called LP rounding.

To illustrate the dual fitting technique in this chapter, we revisit the greedy set cover algorithm from Section 9.2 and then extend it to the set multicover problem, which requires us to cover every element in the universe more than once.