I have been reading the Approximations Algorithm book by Vazrani. It is interesting to note how Duality concepts in optimization play a crucial role in designing approximation algorithm techniques. Chapter 12 in the book talks about such methods. Before we discuss them, let us refresh our minds on duality principles.
1. Primal and Dual Problem: Every LP (primal) has another version (dual), such that the dual of the dual problem is the primal problem. If the primal is a minimization (maximization) problem then the dual is a maximization (minimization) problem.
2. Duality theorem: The primal problem has a finite optimum iff its dual has a finite optimimum. Moreover, if x* and y* are the optimal primal and dual solutions respectively, then the objective values c.x* = b.y*
3. Complementary slackness theorem: Let x and y be primal and dual feasible solutions respectively, then they are both optimal iff the following conditions are satisfied:
- Primal complementary slackness:- Either the primal variable is zero or the corresponding dual constraint is held tight.
- Dual complementary slackness:- Either the dual variable is zero or the corresponding primal constraint is held tight.
NP Hard problems can be stated as integer programs and the linear relaxation of these problems provides us automatically with a lower bound. The polyhedron defining the solution set need not have integer vertices. Our goal then is to find a near-optimal integer solution from the fractional solution (provided by LP relaxation).
The following algorithm design techniques are based on the concepts discussed above:
(1) The most intuitive technique is “rounding”. We convert our fractional solution to the nearest integral solution.
(2) The more interesting technique is “primal-dual schema”. The LP relaxation is referred to as the primal problem. An integral solution to the primal and a feasible solution to its dual are calculated iteratively and compared. Note that a feasible solution to the dual provides a lower bound for the optimal solution.
For examples on how these techniques are used in practice, refer to Chapters 14 and 15 in the book.
Question: Rounding is a better technique than the primal-dual schema because a primal optimal solution provides a tighter bound than a dual feasible solution. True or False?
Answer: Not true!
The reason is the integrality gap of an LP relaxation (problem P). Let OPT(I,f) denote the cost of an optimal fractional solution for an instance I of P. Then integrality gap/ratio is defined as:
sup over I: OPT(I) / OPT(I,f)
When the integrality gap is 1, the LP-relaxation is called an exact relaxation.
The main factor used to compare performances of techniques discussed in (1) and (2) is running time. While, the rounding method needs to find an optimal solution, the primal-dual schema method exploits the combinatorial structure specific to the problem and fine tunes parameters to find a feasible dual solution.
Chapter 22 and 24 talk about how solving special variations and generalizations of problems can prove to be useful in finding approximate solution guarantees.
(3) A more complicated method is “dual fitting”. Given the LP relaxation of our problem and its dual (which is infeasible), the method divides the dual by a suitable factor such that the ‘shrunk’ dual is feasible.
Refer to Chapter 13 for an example of this technique.
Hopefully, this post helped you tie together concepts we learnt in different classes and sparked your interest in developing your own algorithm using the techniques given here.
Until next week, Happy blogging!