1
$\begingroup$

So I know from some research I've done that the OPT-IP <= OPT-LP for the maximum coverage problem, however I'm having some difficulty following the explanations I find. Does an example exist where it can be shown OPT-IP < OPT-LP easily?

$\endgroup$
  • $\begingroup$ This question cannot be answered without, at the very least, knowledge of the specific linear program you are referring to. But more importantly, I would be very surprised if this is true. This would mean that the relaxed LP never picks an integer solution, and it's usually easy to show that there are edge cases where the integer solution is optimal; however, no one can know without the specific LP. $\endgroup$ – DreamConspiracy Nov 25 '18 at 11:48
  • $\begingroup$ "following the explanations I find". It would be nice if you can provide a url or reference to the source. Are you able to pinpoint the first statement that you find it hard to follow? $\endgroup$ – Apass.Jack Nov 25 '18 at 15:32
1
$\begingroup$

Does an example exist where it can be shown OPT-IP < 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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.