Difference between revisions of "Help:Trolls on wheels!"
(Recovering wiki) |
Ridgemcghee (talk | contribs) |
||
| Line 12: | Line 12: | ||
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> | 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> | ||
| + | <br/> | ||
| + | <br/> | ||
| + | Counter-example 2 (in case you spot an error in counter-example 1 - see Discussion): | ||
| + | <br/> | ||
| + | <math>U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14\}</math> | ||
| + | <br/> | ||
| + | <math>S_1 = \{1, 2, 4, 6, 8, 10, 12, 14\}</math> | ||
| + | <br/> | ||
| + | <math>S_2 = \{3, 5, 9, 11\}</math> | ||
| + | <br/> | ||
| + | <math>S_3 = \{7, 13\}</math> | ||
| + | <br/> | ||
| + | <math>S_4 = \{1, 2, 3, 4, 5, 6, 7\}</math> | ||
| + | <br/> | ||
| + | <math>S_5 = \{8, 9, 10, 11, 12, 13, 14\}</math> | ||
| + | <br/><br/> | ||
| + | There is an optimal solution: <math>S_4, S_5</math> (2 subsets). | ||
| + | <br/> | ||
| + | A greedy algorithm will choose <math>S_1, S_2, S_3</math> (3 subsets): | ||
| + | <br/> | ||
| + | 1. <math>S_1</math> since it contains 8 uncovered elements (more than any other subset) | ||
| + | <br/> | ||
| + | 2. <math>S_2</math> since it then contains 4 uncovered elements (more than any other subset) | ||
| + | <br/> | ||
| + | 3. <math>S_3</math> since it then contains 2 uncovered elements (more than any other subset) | ||
| + | <br/> | ||
Revision as of 09:35, 4 December 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 $
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)
