Lectures 20 and 21 (today and Wednesday)

Danny lectured today on online algorithms, in particular, on ski-rental, list-update, and paging/k-server problems. Some directions to think about, before we briefly return to online algorithms in a post-thanksgiving lecture.

• It is a easy exercise to show that in ski-rental, you cannot do better than 2-r/p using any deterministic algorithm. (I always think of r=1, in which case this is 2-1/p.) Can you get a randomized algorithm that has a competitive ratio bounded away from 2, independent of p?
  
  For example: consider the algorithm that buys at day 2p/3 with probability 1/2, and at day p with the remaining probability 1/2? What is the competitive ratio for this algorithm?
  
  
  
  • If the sequence has length less than 2p/3, we are optimal.
    
  • If the sequence has length i in [2p/3,p), the algorithm's expected cost is 0.5(2p/3+p) + 0.5(i), and the optimal cost is i---giving us c(alg)/c(opt) = (5p/6i + 1/2). For i in this interval, this ratio is bounded above by (5/4+1/2) = 1.75.
  
  
  • If the sequence has length >= p, the algorithm's expected cost is 0.5(2p/3+p) + 0.5(2p-1) <= 5p/6+p = 11/6p. Hence c(Alg)/c(opt) <= 11/6.
  
  
  The worst of the three options is 11/6, which is the competitive ratio for this algorithm. This shows that one can do strictly better than 2 (independent of the value of p) using randomization. How much better can you get for the ski-rental problem using randomization? How do you show lower bounds for randomized online algorithms? More about this in an upcoming lecture.
  


• Note that the analysis for randomized algorithms computes the expected cost of the online algorithm for every fixed sequence, and compares that to the best offline algorithm's cost on the same sequence. It is as though the adversary chooses the sequence sigma knowing the algorithm but not the random choices made by the online algorithm---such an adversary is known as an oblivious adversary. We will discuss more about adversary models in a future post.
  


• For the paging problem where you have a set of n pages, but can only store k pages in a cache, the generalization of the cat-and-mouse game is clear: we now have n-k mice and n positions. It's fun to think about what the algorithm for this case should be.
  

For Wednesday's lecture, we will do a quick introduction to approximation algorithms. If you are already familiar with the topic, this lecture may be less useful to you---but it seemed wrong to do a course on algorithms without at least touching upon this topic, and talking about some of the concepts used and the techniques commonly employed.