Difference between revisions of "Help:Trolls on wheels!"

Counter-example 1:

$U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14\}$
$S_1 = \{1, 2, 4, 6, 8, 10, 12, 14\}$
$S_2 = \{3, 5, 9, 11\}$
$S_3 = \{7, 13\}$
$S_4 = \{1, 2, 3, 4, 5, 6, 7\}$
$S_5 = \{8, 9, 10, 11, 12, 13, 14\}$

There is an optimal solution: $S_4, S_5$ (2 subsets).
A greedy algorithm will choose $S_1, S_2, S_3$ (3 subsets):
1. $S_1$ since it contains 8 uncovered elements (more than any other subset)
2. $S_2$ since it then contains 4 uncovered elements (more than any other subset)
3. $S_3$ since it then contains 2 uncovered elements (more than any other subset)

Counter-example 2:

$U = \{1, 2, 3, 4, 5\}$
$S_1 = \{1, 2, 3\}$
$S_2 = \{1, 2, 4\}$
$S_3 = \{4, 5\}$

There is an optimal solution $S_1, S_3$.
But the greedy algorithm might choose $S_2, S_3, S_1$.

Counter-example 3:

$U = \{1, 2, 3, 4, 5, 6\}$
$S_1 = \{2, 3, 4, 5\}$
$S_2 = \{1, 2, 3\}$
$S_3 = \{4, 5, 6\}$

There is an optimal solution: $S_2, S_3$ (2 subsets).
A greedy algorithm will choose $S_1, S_2, S_3$ (3 subsets)