Tag Archives: primal-dual

CS261 Lecture 7: Rounding Linear Programs

Posted on by
Reply

In which we show how to use linear programming to approximate the vertex cover problem.

1. Linear Programming Relaxations

An integer linear program (abbreviated ILP) is a linear program (abbreviated LP) with the additional constraints that the variables must take integer values. For example, the following is an ILP:

\displaystyle \begin{array}{ll} {\rm maximize} & x_1 - x_2 + 2x_3 \\ {\rm subject\ to} \\ & x_1- x_2 \leq 1\\ & x_2 + x_3 \leq 2\\ & x_1 \in {\mathbb N}\\ & x_2 \in {\mathbb N}\\ & x_3 \in {\mathbb N} \end{array} \ \ \ \ \ (1)

Where {{\mathbb N} = \{ 0,1,2,\ldots \}} is the set of natural numbers. The advantage of ILPs is that they are a very expressive language to formulate optimization problems, and they can capture in a natural and direct way a large number of combinatorial optimization problems. The disadvantage of ILPs is that they are a very expressive language to formulate combinatorial optimization problems, and finding optimal solutions for ILPs is NP-hard.

If we are interested in designing a polynomial time algorithm (exact or approximate) for a combinatorial optimization problem, formulating the combinatorial optimization problem as an ILP is useful as a first step in the following methodology (the discussion assumes that we are working with a minimization problem):

  • Formulate the combinatorial optimization problem as an ILP;
  • Derive a LP from the ILP by removing the constraint that the variables have to take integer value. The resulting LP is called a “relaxation” of the original problem. Note that in the LP we are minimizing the same objective function over a larger set of solutions, so {opt(LP) \leq opt(ILP)};
  • Solve the LP optimally using an efficient algorithm for linear programming;
    • If the optimal LP solution has integer values, then it is a solution for the ILP of cost {opt(LP) \leq opt (ILP)}, and so we have found an optimal solution for the ILP and hence an optimal solution for our combinatorial optimization problem;
    • If the optimal LP solution {x^*} has fractional values, but we have a rounding procedure that transforms {x^*} into an integral solution {x'} such that {cost(x') \leq c\cdot cost(x^*)} for some constant {c}, then we are able to find a solution to the ILP of cost {\leq c\cdot opt(LP) \leq c\cdot opt(ILP)}, and so we have a {c}-approximate algorithm for our combinatorial optimization problem.

In this lecture and in the next one we will see how to round fractional solutions of relaxations of the Vertex Cover and the Set Cover problem, and so we will be able to derive new approximation algorithms for Vertex Cover and Set Cover based on linear programming.

Continue reading →