12. Approximation via the Primal-Dual Schema

In Chapters 5–7, we have seen examples of algorithms that solve combinatorial optimization problems optimally using the primal-dual schema. The idea was to maintain an infeasible primal solution (a preflow, pseudo-flow or non-perfect matching) and a feasible dual solution (the height function or potential function). The two solutions satisfy complementary slackness at all times. Each iteration of the algorithm then moves the primal solution closer to feasibility while updating the dual solution to maintain complementary slackness and also keeping the dual solution feasible. Once the primal solution is feasible, we have a feasible primal solution, a feasible dual solution, and the two solutions satisfy complementary slackness. By Theorem 4.5, both solutions are therefore optimal solutions of their respective LPs.

It turns out that we can use the same strategy to obtain approximation algorithms for some NP-hard optimization problems. Obviously, we should not expect to obtain feasible primal and dual solutions that satisfy complementary slackness because this would imply that the solutions we compute are in fact optimal, not just approximations of optimal solutions. Instead, we compute feasible primal and dual solutions that satisfy a relaxed form of complementary slackness. The more we relax the complementary slackness conditions, the greater the gap between the computed primal and dual solutions can be. This gap determines the approximation ratio that the algorithm is guaranteed to achieve.

• In Section 12.1, we introduce this relaxed form of complementary slackness.

• In Section 12.2, we use the set cover problem once again as a familiar problem that we can solve approximately using the primal-dual schema.

• In Section 12.3, we discuss the uncapacitated metric facility location problem as a second application of the primal-dual schema. Our solution to the uncapacitated metric facility location problem introduces a common twist in approximation algorithms based on the primal-dual schema: The first phase of the algorithm constructs feasible primal and dual solutions, but the primal solution is too costly to be paid for by the dual solution. The second phase of the algorithm deletes parts of the primal solution and we prove that this moves the primal solution to within some guaranteed factor of the dual solution. This approach is called primal-dual schema with deletion.