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