CSC 341 (Fall 2021)

Lab: Approximation with Linear Programming

In class, we introduced the problem of 0-1 integer programming.

Suppose we have an objective function over \(m\) variables \(f(x_1, \ldots, x_m) = c_1 x_1 + \cdots + c_m x_m\). Furthermore, suppose we have constraints on the variables in the form of \(n\) equations of the form \(a_{i1} x_1 + \cdots + a_{im} x_m \leq b_i\) for \(i \in 1, \ldots, n\). In addition, we require that the variables can only take on the values \(0\) or \(1\).

Our goal is to choose values for \(x_1, \ldots, x_m\) that maximizes \(f(x_1, \ldots, x_m)\) while satisfying all of the \(n\) constraint equations.

We discussed how the 0-1 integer programming can serve as a reduction point for a variety of problems. We then discussed how we can reduce a problem, e.g., the set cover problem:

Let \(S_1, \ldots, S_m \subseteq \mathcal{U}\) be subsets drawn from a universe \(\mathcal{U}\). Furthermore, assign to each subset a weight \(w_i\) for \(i \in 1, \ldots, m\). Create a sub-collection of these subsets such that:

  • The subsets cover all the elements of \(\mathcal{U}\). In other words, if \(T\) is the collection of subsets, then we want \(\bigcup_{S \in T} S = \mathcal{U}\).
  • The sum of the weights of the sub-collection should be minimal.

An approximation algorithm comes from:

  1. Reducing set cover to 0-1 integer programming.
  2. Solving the resulting integer program as a linear program, a process called linear relaxation.
  3. Recovering an approximate solution for the integer program from the linear program.

For now, let’s focus on the first step of the process. Give a polynomial time reduction from 0-1 integer programming to set cover.