CS261 Lecture 7: Rounding Linear Programs

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

CS261 Lecture 1: Overview

In which we describe what this course is about and give two simple examples of approximation algorithms

1. Overview

In this course we study algorithms for combinatorial optimization problems. Those are the type of algorithms that arise in countless applications, from billion-dollar operations to everyday computing task; they are used by airline companies to schedule and price their flights, by large companies to decide what and where to stock in their warehouses, by delivery companies to decide the routes of their delivery trucks, by Netflix to decide which movies to recommend you, by a gps navigator to come up with driving directions and by word-processors to decide where to introduce blank spaces to justify (align on both sides) a paragraph.

In this course we will focus on general and powerful algorithmic techniques, and we will apply them, for the most part, to highly idealized model problems.

Some of the problems that we will study, along with several problems arising in practice, are NP-hard, and so it is unlikely that we can design exact efficient algorithms for them. For such problems, we will study algorithms that are worst-case efficient, but that output solutions that can be sub-optimal. We will be able, however, to prove worst-case bounds to the ratio between the cost of optimal solutions and the cost of the solutions provided by our algorithms. Sub-optimal algorithms with provable guarantees about the quality of their output solutions are called approximation algorithms.

The content of the course will be as follows:

Continue reading