Help:Trolls on wheels!

From Algorithm Wiki
Revision as of 18:13, 11 September 2014 by Algowikiadmin (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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>