Computer Science 789 Online Algorithms

Fall 1999 Assignment 2

Due in class October 7, 1999.

  1. Prove that MRUS_m is 2-competitive for all m.
  2. Really finish Problem 3 from Assignment 1, that is, prove the Game Graph Lemma.
  3. Find the competitiveness of MARK for the special case that k=2. (This is really two problems. You must prove both a lower bound and an upper bound for the competitiveness of MARK, and they should be the same number.)
  4. Prove the competitivenesses (lower and upper bounds) of MIXED_m for every m. This is Lemma 4 in Handout 5.

Back to Course Page

Back to Assignment Page