1. IP and LP Formulation of Set Cover SC:

The Set Cover Problem:
Given a set V = {1, 2, ..., n} and a collection E of
subsets of V, E = {H_1, H_2, dots, H_m}, we want to find
a minimum size subset S of V that intersects with every H_j.

Intuitively this is a generalization of vertex cover:
In fact, the Set Cover Problem where |H_j| = 2 for all j is just
the Vertex Cover Problem: The vertices of the graphs are 1,2,...,n,
and the edges are H_j.

The problem is NP-complete. The following IP Formulatin actually
shows a reduction between Set Cover and Integer Programming.

=============================================================================

The IP Formulation:

Introduce a variable x_i for 1 <= i <= n.
The intended meaning is that x_i = 0 or 1, and x_i is 1
if and only if i is in the (intended) optimal set S.

Minimize Sum_{i=1}^{n} x_i

Subject to:
x_i \in {0, 1}
and
For each subset H_j = {a, b, ..., k}
x_a + x_b + ... + x_k >= 1

=============================================================================

Correctness:

Claim: A set X = {x_1,..., x_n} with smallest Sum_{i=1}^{n} x_i 
if and only if the set S defined by S = {i: x_i = 1}
is a minimum-size subset of V that intersects with every H_j

The Proof of the Claim is easy by noting that 
a) X satisfies the constraints if and only if X intersects every H_j.
b) Sum_{i=1}^{n} x_i is precisely the size of S

It should be noted, however, that the detailed proof has TWO directions:
==> If X minimizes Sum_{i=1}^{n} x_i then S is minimum-size
<== If S is minimum-size, then X has smallest Sum_{i=1}^{n} x_i.

=============================================================================

The LP Formulation

The LP formulation is obtained from the IP formulation by replacing
each constraint x_i \in {0,1} by
	0 <= x_i <= 1


Note that the Claim above is no longer true for the LP formulation.
However, the LP formulation can be solved in polytime, and we can
obtain an approximation to the original Set Cover problem by
rounding the value of an optimal solution to the LP formulation.

For example, as noted before, when |H_j| = 2 for all j, the Set Cover Problem
is just Vertex Cover. The optimal solution to the LP formulation may assign
fraction values between 0 and 1 to x_i.
An approximation can be obtained by "rounding up" x_i to 1 if x_i >= 0.5,
and "rounding down" x_i to 0 otherwise.

For the more general case, where |H_j| may be > 2, the rounding should
be modified appropriately.



=============================================================================

2. A Greedy algorithm for Bin packing (Problem 1 Chapter 11)

The problem:
Given a set of n items with size (volume) s_i (1 <= i <= n) where 0 < s_i < 1,
the problem is to find the smallest number of unit (i.e., size/volume 1) that
can be used to pack all items.


A Greedy Algorithm: the idea
Get a new bin
For each item in the list:
   If there is room in the current bin then put the item in the current bin
   Otherwise get a new bin, and put the item in this new current bin.


Claim: The above greedy algorithm produces a 2-approximation.

Proof:
Let S = s_1 + ... + s_n.

Observation 1:
The optimal number OPT of bins required is at least the ceiling of S, so
OPT >= S.

Observation 2:
In the above algorithm, the total size of items in any two consecutive bins is > 1.

Consider two cases:
a) The algorithm uses 2k bins. Then the total size of all items is > k, i.e. S > k.
Therefore OPT > k.

b) The algorithm uses 2k+1 bins. Again, the total size of all items is > k.
So S > k, therefore OPT > k. Hence OPT >= k+1.


In any case, we have shown that the number of bins computed by the algorithm is < 2OPT.