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

(Removed counter-example one (it's wrong, see discussion page for explanation)) |
m (Trampin' all the way moved page TADM2E 1.6 to Help:Trolls on wheels!) |
||

(4 intermediate revisions by 3 users not shown) | |||

Line 1: | Line 1: | ||

− | Counter-example 1 | + | Counter-example 1: |

<math>U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14\}</math> | <math>U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14\}</math> | ||

Line 37: | Line 37: | ||

<br/> | <br/> | ||

But the greedy algorithm might choose <math>S_2, S_3, S_1</math>. | But the greedy algorithm might choose <math>S_2, S_3, S_1</math>. | ||

+ | |||

+ | Counter-example 3: | ||

+ | |||

+ | <math>U = \{1, 2, 3, 4, 5, 6\}</math> | ||

+ | <br/> | ||

+ | <math>S_1 = \{2, 3, 4, 5\}</math> | ||

+ | <br/> | ||

+ | <math>S_2 = \{1, 2, 3\}</math> | ||

+ | <br/> | ||

+ | <math>S_3 = \{4, 5, 6\}</math> | ||

+ | |||

+ | There is an optimal solution: <math>S_2, S_3</math> (2 subsets). | ||

+ | <br/> | ||

+ | A greedy algorithm will choose <math>S_1, S_2, S_3</math> (3 subsets) |

## Latest revision as of 07:31, 15 April 2019

Counter-example 1:

$ 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)

Counter-example 2:

$ U = \{1, 2, 3, 4, 5\} $

$ S_1 = \{1, 2, 3\} $

$ S_2 = \{1, 2, 4\} $

$ S_3 = \{4, 5\} $

There is an optimal solution $ S_1, S_3 $.

But the greedy algorithm might choose $ S_2, S_3, S_1 $.

Counter-example 3:

$ U = \{1, 2, 3, 4, 5, 6\} $

$ S_1 = \{2, 3, 4, 5\} $

$ S_2 = \{1, 2, 3\} $

$ S_3 = \{4, 5, 6\} $

There is an optimal solution: $ S_2, S_3 $ (2 subsets).

A greedy algorithm will choose $ S_1, S_2, S_3 $ (3 subsets)