Help:Trolls on wheels!

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

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:

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