Difference between revisions of "Help:Trolls on wheels!"
From Algorithm Wiki
(Recovering wiki) |
(No difference)
|
Revision as of 18:13, 11 September 2014
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:
<math>S_1 = \{1, 2\}</math> <br/> <math>S_2 = \{3, 4, 5, 6\}</math> <br/> <math>S_3 = \{7, 8, 9, 10, 11, 12, 13, 14, 15, 16 \}</math> <br/> <math>S_4 = \{1, 2, 3, 4, 5, 6, 7, 8 \}</math> <br/> <math>S_5 = \{9, 10, 11, 12, 13, 14, 15, 16 \}</math>
The greedy algorithm will choose <math>S_3, S_2, S_1</math>, while the optimal solution is simply <math>S_4, S_5</math>
