LP-Based approximation algorithms

by

Sudharshana

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!

About these ads
Both comments and trackbacks are currently closed.

Comments

  • Laura McLay  On April 20, 2011 at 10:27 am

    Good post. When you ask:

    “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?”

    Do you mean in general or for this specific problem?

  • philtheconvex  On April 21, 2011 at 11:05 am

    This has me wondering, Suds: if I remember correctly, we can derive the Complementary Slackness conditions by applying the Karush-Kuhn-Tucker conditions to a linear program. Might it be possible, then, to apply the KKT conditions to problems with more general, nonlinear-but-convex relaxations, to concoct a similar method for developing approximation algorithms to such problems?

    I know there’s duality theory for various kinds of non-linear programming, and I think it’d be cool if we could use it to develop a more general version of how Vazirani proposes using the relaxed Comp. Slackness conditions. One possible complication comes to mind: the duality gap is non-zero in many kinds of non-linear programming problems, so maybe that would place a bound on just how well an algorithm produced by a non-linear version of the primal-dual schema could work..?

  • Sudharshana  On April 21, 2011 at 3:04 pm

    Dr. McLay, The question I asked was in general. Most people believe it to be true. But Vazarani says that sometimes it can be true, but most often the other method performs better.

  • Sudharshana  On April 21, 2011 at 3:08 pm

    Phil, that would be interesting to see if KKT can be used to derive the generalized complementary slackness equations. Convexity would be key though.

  • philtheconvex  On April 25, 2011 at 3:51 am

    I was thinking the same thing about convexity, Suds! Although, in honesty, I am not entirely clear on how important convexity is for applying the KKT conditions; there seem to be a thousand-and-one “constraint qualifications” under which the KKT conditions become not just necessary but also sufficient, and none of the constraint qualifications I’ve seen ever seem to plainly state, “The problem is convex.”! Irritating! But, I’ve seen various online lectures claim the KKT conditions are sufficient for convex problems…

    Anyway, I also had another idea that motivated me to reply here! I’ve been poking away at trying to turn a DP algorithm I’ve built for a simple game theory problem into an approximation algorithm for a more difficult game theory problem; but, a problem I’ve frequently run into is that, in trying to apply the primal-dual schema, I repeatedly find myself building linear relaxations that contain exponentially many constraints. And, of course, we can’t verify in polynomial time that exponentially many, distinct constraints hold or don’t hold, right?

    So, I suppose I was wondering if this is a sign that, short of finding an alternative modeling approach, the problem I was dealing with maybe can’t be deal with via the primal-dual schema…? Whadda ya think?

  • Sudharshana  On May 2, 2011 at 11:19 am

    Hey Phil,
    While doing the primal dual schema, check to see if your conditions will hold tight. If they will then they are not the ones you can relax, so you need to find only those that matter. So maybe you can reduce the exponential number of constraints in your dual to those that matter.
    If you still end up with as many constraints, maybe you can look at it for some special case, and see if you can extend the results to a more general problem later.
    Hope that makes sense. Just my thoughts!
    Good luck with your problem. Research is fun!!!

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: