Computer Science 789 Online Algorithms
Fall 1999 Assignment 2
Due in class October 7, 1999.
-
Prove that MRUS_m is 2-competitive for all m.
-
Really finish
Problem 3 from Assignment 1, that is, prove
the Game Graph Lemma.
-
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.)
-
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