• 6.5210/18.415: Advanced Algorithms
  • PSets
  • Calendar
  • Materials
  • Information
  • Online Algorithms Continued

    Lecturer: David Karger
    Scribe: Tushara C. Karunaratna

    November 1, 2004


    In the previous lecture, we defined the term competitive ratio for deterministic online algorithms. We studied a 2-competitive algorithm for ski-rental. We also observed that our greedy algorithm for load balancing is a 2-competitive online algorithm.

    In this lecture, we will study online algorithms for paging, finance, and \(k\)-server on a line.


    Paging is an important problem in computer systems design. We model a machine’s memory as consisting of two parts: an unlimited number of pages of slow memory, and a cache consisting of \(k\) pages of fast memory. On a page request, if the requested page is not in the cache (we call this a cache miss or a fault), then a page in the cache must be evicted and the requested page must be brought in. A paging strategy specifies the choice of which page to evict on a cache miss. The goal is to minimize the number of cache misses.

    Here are the some of the commonly used paging strategies.

    LRU is \(k\)-competitive

    To analyze the performance of LRU, we partition the input sequence into phases. The first phase begins immediately after LRU first faults. A phase ends immediately after LRU has faulted \(k\) times since the start of the phase; the next phase begins at this point.

    We now prove that OPT faults at least once per phase.

    Consider any phase such that LRU faults twice on some page \(p\) in this phase. We know that at least \(k\) other distinct pages must have been requested in between the two requests of \(p\) (because otherwise \(p\) would not have been evicted by LRU). Hence, there are at least \(k+1\) distinct pages requested in this phase, and thus OPT faults at least once in this phase.

    On the other hand, consider any phase such that LRU faults on \(k\) distinct pages in this phase. Let \(p\) be the last fault of the previous phase. Note that even if \(p\) is one of the \(k\) faults in this phase, at least \(k\) other distinct pages must have been requested in this phase (because otherwise \(p\) would not have been evicted by LRU). Since \(p\) was in OPT’s cache at the start of this phase, OPT faults at least once in this phase.

    Therefore, LRU is \(k\)-competitive.

    Lower Bound for Deterministic Online Paging

    Consider any deterministic online paging algorithm \(A\).

    We construct a request sequence involving \(k+1\) pages; at each step, we request the page that is not in \(A\)’s cache. Note that for this sequence, \(A\) faults on every request.

    Consider the offline algorithm that, on a cache miss, evicts the page that is requested furthest in the future. When this offline algorithm faults, the page that it evicted won’t be requested until at least \(k\) steps in the future. Therefore, this offline algorithm faults only once every \(k\) requests for our above adverserial sequence.

    Therefore, no deterministic online paging algorithm can be better than \(k\)-competitive.


    We own some amount of stock. We have no information on how the price per unit of the stock may fluctate in the future, but we know that the maximum possible price is \(M\) and that the minimum price is \(m\). We want to sell our stock so as to maximize our return.

    Reserve price algorithm

    The stategy is to sell all our stock the first time that the price beats \(r\).
    We claim that \(r=\sqrt{Mm}\) is a good choice:

    \(\max\{r/m, M/r\}\) is minimized by setting \(r/m = M/r\). This gives us \(r = \sqrt{Mm}\). With this choice of \(r\), the regret ratio is \(\sqrt{M/m}\).

    Selling in fractions

    We assume that \(M = 2^k m\) for some integer \(k\).
    Let OPT denote the maximum price that is reached (of course, we do not know this in advance).

    Consider the following strategy: for each \(i\) where \(1 \le i \le k\), sell \(1/k\) of our stock the first time that the unit price falls in the interval \([2^i\, m, 2^{i+1} \,m)\).

    Let \(j\) be the largest integer such that \(2^j\, m \le\)OPT. Note that \(2^j\, m > OPT/2\).

    Therefore, we sell \(1/k\) of our stock at price at least \(OPT/2\).

    So our regret ratio is \(\frac{OPT}{OPT/(2k)} = 2k = 2\log(M/m)\).

    A randomized reserve-price strategy

    We pick \(i\) uniformly at random from \(1, 2, \ldots, k\). We set the reserve price to \(2^i \,m\).

    Let \(j\) be the largest integer such that \(2^j\, m \le\)OPT. With probability at least \(1/k\), we have a revenue of \(2^j\, m > OPT/2\). Therefore, our expected revenue is at least \(OPT/2k\).

    So our expected regret ratio is \(2k = 2\log(M/m)\).

    \(k\)-server on a line

    We have \(k\) servers on a line. A request specifies a point on the line to which a server must be moved. The cost of serving a request sequence is measured by the total distance traveled by servers. Thus, the goal is to be clever in the way servers are moved, such that the total distance traveled by the servers is minimized.

    A greedy strategy that isn’t competitive

    A greedy strategy for this problem is to simply move the server that is closest to the requested point.

    However, we can easily see that this greedy strategy is not competitive. Suppose that we have two servers \(A\) and \(B\) that are initially at points \(x\) and \(y\), respectively, with \(x<y\). Suppose that our requests repeatedly alternate between the points \(y-(y-x)/4\) and \(y+(y-x)/4\). Then, according to the greedy strategy, all the requests will be served by \(B\), and the total distance traveled will be infinite. A better strategy would be to first move \(A\) and \(B\) to our two request points, in which case the total distance traveled would be only constant.

    Double coverage

    The Double Coverage (DC) strategy is

    Now, we show that DC is \(k\)-competitive.

    We compare the moves of DC to those of an optimal offline algorithm OPT. We can assume that OPT satisfies a request by moving exactly one server; we can convert any offline strategy into a strategy that moves exactly one server per request, without increasing the cost, by deferring moves to the future.

    Let \(M\) be the cost of the minimum cost matching between DC’s and OPT’s servers.
    Let \(S\) be the sum of the pairwise distances of DC’s servers.
    Let \(\Phi = k\cdot M + S\). This is our potential function.

    We consider the requests one by one. For each request, we first observe OPT’s move, and then we observe DC’s move. We compute the amortized cost incurred by DC for each move.

    Note that positive amortized cost is incurred by DC only when OPT moves. When OPT moves, the amortized cost incurred by DC at most \(k\) times the distance moved by OPT’s server.

    Thus, the total real cost incurred by DC is at most \(k\) times that incurred by OPT (plus some additional constant if the potential was not initially 0).

    So, DC is \(k\)-competitive.

    1. The competitive ratio of a randomized algorithm is the ratio between its expected cost and cost of the OPT.↩︎