Difference between revisions of "Help:Trolls on wheels!"
From Algorithm Wiki
(Recovering wiki) |
(Recovering wiki) |
||
| Line 1: | Line 1: | ||
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: | 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 | + | 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> |
Revision as of 18:22, 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:
$ 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 $
