CS 466/666

Monday November 26

To sign up for a problem, send email to alubiw "at" uwaterloo.ca. I will update this list to indicate the first person who signs up.
  1. [Jeffrey Cheng] Prove that the First Fit algorithm for online bin packing has approximation ratio 2, i.e. prove FF(I) <= 2 OPT(I) where FF(I) is the number of bins used by First Fit on input I, and OPT(I) is the optimum number of bins for input I.

  2. [Grace Wang] The same for Best Fit.

  3. [Curt Gallagher]] Recall that we showed in class that offline bin packing has a poly time approximation scheme with asymptotic approximation ratio 1+epsilon. The qualifier ``asymptotic'' is crucial: Prove that there is no polynomial time approximation algorithm for off-line bin packing with approximation ration less than 1.5 unless P=NP. Hint: Consider 2 bins.

  4. [Adrian Kwok] Show how to implement First Fit in O(n log n) time.

  5. [Darin Tay] In the SUBSET SUM problem you are given a set of integers s_1, s_2, ..., s_n, and a number k; the question is whether there is a subset of the s_i's with sum exactly k. Is SUBSET SUM strongly NP-complete, or is there a pseudo-polynomial time algorithm? Justify.