Monday December 3
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.
- [Jeremy Bibby]
For the robot navigation problem described in Problem Session 7, consider
Algorithm 2, that does doubling after choosing a random initial direction.
Prove that the expected distance travelled is at most 7d.
-
[William Finlay]
Show that the paging algorithm LFU (Least Frequently Used)
has unbounded competitive ration.
-
[Jan Zantinge]
Show that no deterministic on-line paging algorithm has competitive
ratio less than k.
-
[Tomasz Jaroszewski]
Show that Fiat's randomized on-line paging algorithm can in the worst
case have competitive ratio at least k.
-
[Reilly Watson]
Show that the local greedy algorithm for the k-server problem has
unbounded competitive ratio even for 3 request points and 2 servers.