Problem Set #2 (PRELIMINARY)

CS 255
due March 14, 2001

  1. Show that the relative error bound for the approximation algorithm of the text for the vertex cover problem is no better than 2.

  2. Show that the relative error bound for the first fit decreasing (FFD) approximation algorithm for the bin packing problem is no better than 1.5.

  3. Trace the approximation algorithm for subset sum problem of Section 37.4 on the instance with set {37,31,29,23,19,17} and target 111, for both epsilon = 0.18 and epsilon=0.12.

  4. ??