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:
Where 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
;
- 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
, 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
has fractional values, but we have a rounding procedure that transforms
into an integral solution
such that
for some constant
, then we are able to find a solution to the ILP of cost
, and so we have a
-approximate algorithm for our combinatorial optimization problem.
- If the optimal LP solution has integer values, then it is a solution for the ILP of cost
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.