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

One counter-example consists of a series of subsets that increase in size exponentially, plus 2 additional subsets that each cover half of the elements. Example:

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

The greedy algorithm will choose $S_3, S_2, S_1$, while the optimal solution is simply $S_4, S_5$

Counter-example 2 (in case you spot an error in counter-example 1 - see Discussion):
$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)