> For the complete documentation index, see [llms.txt](https://evarga.gitbook.io/sh-intro-to-algs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://evarga.gitbook.io/sh-intro-to-algs/part-vii-selected-topics/27.-online-algorithms.md). # 27. Online Algorithms ## Exercises ### 27.1-1 The cost function is $$ h(m) = \begin{cases} m + 1 & \text{if } m \le p \ p + k & \text{if } m > p \end{cases}. $$ Assuming $$B$$ is sufficiently large and $$k>1$$, the competitive ratio is $$ c(p,k) = \begin{cases} \cfrac{p+k}{p+2} = 1 + \cfrac{k-2}{p+2} & \text{if } 0 \le p \le k - 2 \\\[0.5cm] \cfrac{p+k}{k} = 1 + \cfrac{p}{k} & \text{if } k - 1 \le p < B \end{cases}. $$ You should choose $$p = k - 2$$. The competitive ratio is minimized at $$2 - \frac{2}{k}$$. ### 27.1-2 Let $$k = \lceil b/r \rceil$$ be the threshold day and $$m$$ the number of times you ski. The cost function is $$ h(m) = \begin{cases} r\*m & \text{if } m < k \ r(k-1)+b & \text{if } m \ge k \end{cases}. $$ The competitive ratio is $$\frac{(k-1)r + b}{b} < \frac{b + b}{b} = 2$$. ### 27.1-3 Let $$n$$ be the total number of pairs. An optimal offline player who knows the locations of all cards in advance will simply turn over matching pairs on every single turn. This optimal cost is exactly $$n$$ rounds. The two-stage algorithm is as follows: * **Stage 1:** You systematically select pairs of unrevealed cards. Since there are $$2n$$ total cards and you reveal 2 per round, it takes exactly $$n$$ rounds to expose every card on the board. During this phase, you might accidentally uncover $$k$$ matching pairs (where $$k ≥ 0$$), which are immediately removed. * **Stage 2:** You now have perfect memory of the remaining $$2n - 2k$$ cards on the board. Because you know exactly where every match is, you spend one round per remaining pair to clear them. This takes exactly $$n - k$$ rounds. The total number of rounds required by this algorithm is the sum of both stages: $$n + (n - k) = 2n - k$$. The worst-case scenario occurs when you make zero accidental matches in the first stage. In this case, the total number of rounds peaks at $$2n$$. Comparing this to the optimal baseline, the competitive ratio is the maximum value of $$(2n - k) / n$$. At its worst, this simplifies to $$2n / n = 2$$. ### 27.2-1 Let $$C\_k$$ be the random variable denoting the cost of the $$k$$th operation. Therefore, the total cost is $$C=\sum C\_k$$, hence by the linearity of expectation, we have $$ E\[C]=E\left\[\sum\_{k=1}^m C\_k\right]=\sum\_{k=1}^m E\[C\_k]=\sum\_{k=1}^m \sum\_{i=1}^n p(x\_i)r\_L(x\_i)=m \sum\_{i=1}^np(x\_i)r\_L(x\_i). $$ Suppose for the sake of contradiction that $$E\[C]$$ attains its minimum, yet the list $$L$$ is not sorted in decreasing order of probability. Thus, there are at least two elements, $$x$$ and $$y$$, where $$p(x) > p(y)$$ and $$r\_L(x) > r\_L(y)$$. By swapping these elements in the list we can obtain a smaller value of $$E\[C]$$. This contradicts the statement that it has a minimum value. Therefore, the sum is minimized when the elements of $$L$$ are sorted in decreasing order with respect to $$p(x\_i)$$. ### 27.2-2 Professor Carnac is wrong. Let $$L={1,2}$$ be the initial list and the search sequence be $$(1,2)$$. The `FORESEE` algorithm may choose to move 2 to front in the first call, such that the next search would incur a minimum cost. But `MOVE-TO-FRONT` would not swap elements in the first call. Therefore, it would have a lower cost in this iteration. ### 27.2-3 The algorithm based on frequency counts is not O(1)-competitive. We can prove this by demonstrating that the algorithm's competitive ratio grows linearly with the size of the list $$n$$, meaning there is no constant boundary that holds true for all list sizes. We do this by constructing a sequence where the Frequency-Count (FC) algorithm performs significantly worse than the Move-To-Front (MTF) algorithm (and by extension, the optimal offline algorithm). #### The Counterexample Assume an initial list of $$n$$ elements $$x\_1, x\_2, \dots, x\_n$$. Let $$k$$ be an arbitrarily large integer. We execute a search sequence in two phases: * **Phase 1 (The Setup):** We search for $$x\_1$$ exactly $$k$$ times, then $$x\_2$$ exactly $$k$$ times, continuing this pattern up to $$x\_{n-2}$$. * By the end of this phase, elements $$x\_1$$ through $$x\_{n-2}$$ all have a frequency count of $$k$$. * Elements $$x\_{n-1}$$ and $$x\_n$$ have a frequency count of 0 and are cemented at the very back of the list (positions $$n-1$$ and $$n$$). * **Phase 2 (The Penalty):** We issue a sequence alternating between the last two elements for a total of $$k-1$$ searches. #### Cost Analysis The total cost of the FC algorithm is $$ \underbrace{k \sum\_{i=1}^{n-2} i}*{\text{phase 1}} +\underbrace{k(n-1)}*{\text{phase 2}}= \Omega(kn^2). $$ The total cost of the MTF algorithm is $$ \underbrace{\sum\_{i=1}^{n-2} (i + k - 1)}*{\text{phase 1}} +\underbrace{(2n - 1) + 2(k-3)}*{\text{phase 2}} = \ \Omega(kn + n^2). $$ Letting $$k \to \infty$$, the competitive ratio becomes$$\ \Omega(n)$$. This is not a constant, since it depends on $$n$$. ### 27.2-4 Using the hint from the book, we should drop the multiplicative factor 2 in the potential function. The actual cost of the $$i$$th `MOVE-TO-FRONT` operation, is given by equation $$c\_i^M = r\_{L\_{i-1}^M}(x).$$ Similarly, the actual cost of the $$i$$th `FORESEE` operation, is given by equation $$c\_i^F = r\_{L\_{i-1}^F}(x).$$ The new model restricts `FORESEE` to only moving the accessed element $$x$$ earlier in the list. Because the potential function evaluates `MOVE-TO-FRONT`'s changes before `FORESEE`'s changes, $$x$$ is already sitting at the very front of $$L^M$$. This means $$x$$ is currently before every element in MTF's list. Any element $$y$$ that FORESEE moves $$x$$ past must have been before $$x$$ in $$L^F$$. Moving $$x$$ past $$y$$ in $$L^F$$ aligns their relative order perfectly with $$L^M$$, which strictly destroys an inversion. Because FORESEE's moves can only destroy inversions, its potential change is always zero or negative $$\Delta\Phi\_{FORESEE} \le 0$$. Effectively, this is like setting $$t\_i=0$$ in the original proof. Substituting all these details into the derivation of equation (27.8) we get $$\hat c\_i^M \le 2c\_i^F$$. The rest of the proof again matches Theorem 27.1. {% hint style="info" %} The clause *"assuming that the number of requests is sufficiently large"* of this exercise allows the algorithms to start with different lists (which creates an initial potential difference) and relies on a long sequence of requests to wash out that initial constant mathematically. {% endhint %} ### 27.3-1
RequestCacheMissesEpoch
1111
21,221
12,121
52,1,531
41,5,442
41,5,442
15,4,142
24,1,252
41,2,452
21,4,252
34,2,363
42,3,463
53,4,573
24,5,284
24,5,284
15,2,194
25,1,294
25,1,294
### 27.3-2 We just need a little bit different setup for showing the lower bound and then we can reuse the proof of Theorem 27.2. Suppose that the input consists of $$k + 1$$ blocks, numbered $$1, 2, \dots, k + 1$$, and the request sequence is $$ 1, 2, 3, 4,\dots,k-1, 1, 2, 3, 4,\dots,k-1, k, k + 1, k, k + 1, k, k + 1,\dots , $$ where after the initial $$1, 2, 3, 4,\dots,k-1, 1, 2, 3, 4,\dots,k-1$$, the remainder of the sequence alternates between $$k$$ and $$k+1$$, with a total of $$n$$ requests. Following the steps of the proof in Theorem 27.2, we may conclude that the competitive ratio is $$(n-(k-1))/(k+1)=\Omega(n/k)$$. ### 27.3-3 Virtually the whole proof of Theorem 27.3 can be reused. The only difference between LRU and FIFO is which elements are evicted from the cache. But this doesn't alter the core of the proof, since none of them incurs more than $$k$$ misses per epoch. ### 27.3-4 See the reasoning in the previous exercise. The logic maps perfectly because the mechanics of `MARKING` inherently enforce the exact same epoch boundaries as the standard proof. ### 27.3-5 We can reuse the proof of Theorem 27.4 by tweaking the setup. In order to make room in the cache for block $$k + 1$$, the online algorithm evicts some block $$b\_i$$ from the cache not inside the lookahead window of size $$l$$. The adversary issues $$l$$ subsequent requests for this same block $$k + 1$$. Essentially, the adversary pads the lookahead window with a single block. Knowing that the online algorithm has just evicted block $$b\_i$$, the adversary makes the request following the current window be for $$b\_i$$. Then this pattern is repeated. On average, the online algorithm incurs a cache miss on every $$(l+1)$$th request and therefore incurs $$n/(l+1)$$ cache misses over the $$n$$ requests. This entails a competitive ratio at least $$k/(2(l+1))=\Omega(k)$$, since $$l$$ is a constant. ## Problems ### 27-1 Cow-path problem Read the paper [An Optimal Randomized Algorithm for the Cow-Path Problem](https://dl.acm.org/doi/pdf/10.5555/313559.313848), which describes a simple randomized online algorithm for this problem (set $$\omega=2$$). ### 27-2 Online scheduling to minimize average completion time #### a. To prove that the online Shortest Processing Time (SPT) algorithm is not $$d$$-competitive for any constant $$d$$, we can construct an adversarial sequence of tasks where the ratio of the online algorithm's cost to the optimal offline cost exceeds $$d$$. Let $$k$$ be an arbitrarily large integer such that $$k \ge d$$, and let $$M$$ be a massive processing time ($$M \gg k$$). Consider a sequence of $$n = k+1$$ tasks with the following release times and processing times: * **Task 1:** $$r\_1 = 0$$, $$p\_1 = M$$ * **Tasks 2 through** $$k+1$$**:** $$r\_i = 1$$, $$p\_i = 1$$ **Cost of the Online SPT Algorithm** At time $$t=0$$, the machine is idle and only Task 1 is available. The SPT algorithm immediately starts Task 1. Because tasks cannot be preempted, Task 1 occupies the machine completely until time $$M$$. By time $$M$$, Tasks 2 through $$k+1$$ have been waiting since $$t=1$$. SPT schedules these remaining $$k$$ tasks consecutively. Their completion times will be $$M+1, M+2, \dots, M+k$$. The total sum of completion times for SPT is:

\sum C_{SPT} = M + \sum_{j=1}^{k} (M + j) = M + kM + \frac{k(k+1)}{2} = M(k+1) + O(k^2).

**Cost of the Optimal Offline Algorithm (OPT)** An optimal offline algorithm knows the future release times. It will intentionally remain idle from $$t=0$$ to $$t=1$$. At $$t=1$$, all tasks are available. OPT minimizes average completion time by scheduling the $$k$$ short tasks first, followed by the massive task. The short tasks complete at times $$2, 3, \dots, k+1$$. Task 1 then starts at $$k+1$$ and completes at $$M+k+1$$. The total sum of completion times for OPT is:

\sum C_{OPT} = \sum_{j=1}^{k} (j + 1) + (M + k + 1) = M + O(k^2).

**The Competitive Ratio** To find the competitive ratio, we divide the cost of the SPT algorithm by the cost of the optimal algorithm:

\frac{\sum C_{SPT}}{\sum C_{OPT}} = \frac{M(k+1) + O(k^2)}{M + O(k^2)}.

If we fix $$k$$ and let the processing time $$M$$ approach infinity, the quadratic terms become negligible. The ratio evaluates to:

\lim_{M \to \infty} \frac{M(k+1)}{M} = k + 1.

Because $$k$$ is the number of small tasks, an adversary can choose $$k$$ to be arbitrarily large. Consequently, for any proposed constant $$d$$, the adversary can simply generate an instance with $$k \ge d$$ short tasks, guaranteeing a competitive ratio of at least $$d+1$$. Therefore, the non-preemptive online SPT algorithm is not $$d$$-competitive for any constant $$d$$. #### b. To run Shortest Remaining Processing Time (SRPT) as an online algorithm, the system must continuously monitor and react to two specific types of events: the arrival of a new task and the completion of a currently running task. The algorithm maintains a pool of all tasks that have been released but have not yet completed, tracking the remaining processing time for each. * **When a new task arrives (at time** $$r\_i$$ **with processing time** $$p\_i$$**):** The algorithm adds the new task to the available pool. It then compares $$p\_i$$ to the remaining processing time of the currently running task. If the new task's processing time is strictly less than the currently running task's remaining time, the algorithm preempts (pauses) the current task, updates its remaining time, and immediately begins executing the new task. Otherwise, the current task continues running and the new task waits in the pool. * **When the current task completes:** The algorithm removes the finished task from the pool. If there are other tasks waiting, it examines the available pool, selects the task with the absolute smallest remaining processing time, and resumes (or starts) executing it. If the pool is empty, the machine remains idle until the next task arrives. By strictly re-evaluating the schedule at these two event triggers, the machine guarantees that at any arbitrary moment $$t$$, it is always processing the available task with the absolute shortest remaining time, without needing to know any future task arrivals. #### c. The proof relies on the fact that SRPT is the optimal algorithm for the preemptive version of the scheduling problem, meaning it produces the absolute minimum possible sum of completion times among all valid preemptive schedules (see [Problem 15-2(b)](/sh-intro-to-algs/part-iv-advanced-design-and-analysis-techniques/15.-greedy-algorithms.md#id-15-2-scheduling-to-minimize-average-completion-time)). Let $$S\_P$$ denote the set of all valid preemptive schedules for a given set of tasks, and let $$S\_N$$ denote the set of all valid nonpreemptive schedules. Because a nonpreemptive schedule is simply a preemptive schedule that happens to perform zero preemptions, the set of nonpreemptive schedules is a subset of the set of preemptive schedules $$S\_N \subseteq S\_P$$. Since SRPT minimizes the sum of completion times over the entire set $$S\_P$$, its total cost $$\sum\_{i=1}^n C\_i^P$$ must be less than or equal to the cost of any schedule within $$S\_P$$. Because the optimal nonpreemptive schedule is an element of $$S\_N$$, and therefore an element of $$S\_P$$, the cost of the SRPT schedule cannot exceed the cost of the optimal nonpreemptive schedule $$\sum\_{i=1}^n C\_i^\*$$. Thus, $$\sum\_{i=1}^n C\_i^P \le \sum\_{i=1}^n C\_i^\*$$. #### d. By time $$C\_i^P$$, task $$i$$ completes its execution. Because of the strictly ordered renumbering, all prior tasks $$j$$ (where $$j < i$$) must have also completed by this time, since $$C\_j^P < C\_i^P$$. Therefore, by time $$C\_i^P$$, the machine has fully processed all tasks in the set $${1, 2, \dots, i}$$. Because the machine can only process one task at a time, the total time elapsed since $$t=0$$ must be at least the total sum of the processing requirements for all $$i$$ tasks. Thus, $$C\_i^P \ge \sum\_{j=1}^i p\_j$$. A task cannot begin execution, let alone complete, before it is released. Therefore, for any task $$j$$, its completion time must be strictly greater than its release time $$C\_j^P > r\_j$$. Because the tasks are ordered by completion time, $$C\_i^P > C\_j^P$$ for all $$j < i$$. Transitively, this means $$C\_i^P > r\_j$$ for all $$j < i$$. Thus, $$C\_i^P \ge \max{r\_j : j \le i}$$. We can conclude that

C_i^P \ge \max\left\{\sum_{j=1}^i p_j, \max_{j \le i} r_j\right\}.

#### e. We can prove this upper bound by mathematical induction on the task index $$i$$, based on the greedy nonpreemptive scheduling logic defined in step 3 of the algorithm. In the greedy nonpreemptive schedule, the machine processes tasks strictly in the order $$1, 2, \dots, n$$. For any task $$i$$, it begins execution either the moment the previous task $$i-1$$ completes, or at its own release time $$r\_i$$ if the machine has been idle waiting for it. Therefore,

C_i = \max(C_{i-1}, r_i) + p_i.

**Base Case:** For the first task, there is no previous task to wait for, so it simply starts at its release time.

C_1 = r_1 + p_1=\max\{r_j : j \le 1\} + \sum_{j=1}^1 p_j.

**Inductive Step:** Assume the inequality holds for some $$i-1$$:

C_{i-1} \le \max\{r_j : j \le i-1\} + \sum_{j=1}^{i-1} p_j.

We analyze the two possible scenarios for the recurrence relation: **Case 1: The machine does not idle before task** $$i$$ **(**$$C\_{i-1} \ge r\_i$$**)** In this case, task $$i$$ starts immediately after task $$i-1$$ finishes, so $$C\_i = C\_{i-1} + p\_i$$. Substituting our inductive hypothesis:

C_i \le \left( \max\{r_j : j \le i-1\} + \sum_{j=1}^{i-1} p_j \right) + p_i.

Because the maximum release time of the first $$i-1$$ tasks is naturally less than or equal to the maximum release time of the first $$i$$ tasks, we can replace the max term to get:

C_i \le \max\{r_j : j \le i\} + \sum_{j=1}^i p_j.

**Case 2: The machine idles before task** $$i$$ **(**$$C\_{i-1} < r\_i$$**)** In this case, the machine must wait until time $$r\_i$$ to start task $$i$$, so $$C\_i = r\_i + p\_i$$. By definition, $$r\_i \le \max{r\_j : j \le i}$$. Furthermore, because all processing times are non-negative, $$p\_i \le \sum\_{j=1}^i p\_j$$. Substituting these bounds directly yields:

C_i \le \max\{r_j : j \le i\} + \sum_{j=1}^i p_j.

Since the inequality holds in both possible scheduling cases, it holds for all $$i = 1, \dots, n$$. #### f. To convert the offline `COMPLETION-TIME-SCHEDULE` algorithm into an online algorithm, you can run the preemptive SRPT schedule as a simulated background process and use its completion events to feed the actual nonpreemptive machine. Here is how the online modification works: * **Simulate SRPT Online:** Maintain a virtual machine that runs the preemptive SRPT algorithm on the tasks as they are released. As established earlier in part (b), SRPT can be executed perfectly online because it only requires comparing the remaining times of currently released tasks. * **Queue by Virtual Completion:** When a task $$i$$ completes its execution on the *virtual* SRPT machine at time $$C\_i^P$$, it is immediately added to a ready queue for the actual machine. This guarantees that tasks enter the ready queue exactly in the sorted order of their preemptive completion times ($$C\_1^P < C\_2^P < \dots < C\_n^P$$). * **Greedy Nonpreemptive Execution:** The actual machine runs nonpreemptively, solely processing tasks from this ready queue in FIFO order. If the actual machine is idle and the ready queue is empty, it simply waits until the virtual SRPT machine finishes another task. By decoupling the schedule into a virtual preemptive phase and an actual nonpreemptive phase, the algorithm dynamically replicates the renumbering and ordering steps of the offline algorithm without needing to know any future release times. #### g. Substituting the bounds from (d) directly into the inequality from (e) forms the basis of part (f), demonstrating that the algorithm's nonpreemptive completion time for any task is strictly bounded by twice its preemptive completion time:

C_i \le C_i^P + C_i^P = 2C_i^P.

Summing this relationship over all $$n$$ tasks gives the total cost bound for the online algorithm:

\sum_{i=1}^n C_i \le 2 \sum_{i=1}^n C_i^P.

Finally, applying the result from part (c), yields the conclusive inequality:

\sum_{i=1}^n C_i \le 2 \sum_{i=1}^n C_i^*.

Because the total sum of completion times generated by the online `COMPLETION-TIME-SCHEDULE` algorithm is at most twice the total sum of completion times of the optimal offline schedule, the algorithm achieves a competitive ratio of 2.