LP Relaxation of Maximum Coverage Problem
Does an example exist where it can be shown OPT-IP &lt; OPT-LP easily?


Here is an example of "LP Relaxation of Maximum Coverage Problem". 

Let $G$ be the complete graph with four vertices, $\{v_1,v_2,v_3,v_4\}$. That is, $G$ has six edges. Let $S_i$ be the set of edges that is not incident to $v_i$. More specifically,
$S_1=\{\{v_1, v_2\},\{v_1, v_3\},\{v_1, v_4\}\}$.
$S_2=\{\{v_1, v_2\},\{v_2, v_3\},\{v_2, v_4\}\}$.
$S_3=\{\{v_1, v_3\},\{v_2, v_3\},\{v_3, v_4\}\}$.
$S_4=\{\{v_1, v_4\},\{v_2, v_4\},\{v_3, v_4\}\}$.

The maximum coverage problem is given the above 4 sets, select at most 2 of these sets such that the maximum number of elements are covered. The answer is to select any two sets, which will cover 5 elements. For example, if we select $S_1$ and $S_2$, then all edges are covered except edge $\{v_1,v_2\}$.

If we relax this integer linear programming problem to its corresponding general linear programming problem as done here, we can select "half" of each set. Then each element is "covered" exactly once in total! For example, $\{v_1,v_2\}$ is covered by "half" of $S_3$ and "half" of $S_4$. So we are able to "cover" 6 elements, which are more than 5 elements.

As you should be able to see by now, the idea of this example is quite easy to understand and to generalize. 



Problem to ponder (This is not an exercise.)
Is 5/6 the worst ratio we can get given any 4 sets?