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$