Online Algorithms

Prev: Parallel and Distributed Algorithms Next: Number Theory and Algebra

Problems

13.1

Due to D.D. Sleator and R.E. Tarjan [379].

Show that the LRU algorithm for paging is $k$-competitive. What can you say about its competitiveness coefficient?

---

13.2

Due to D.D. Sleator and R.E. Tarjan [379].

Show that the FIFO algorithm for paging is $k$-competitive. What can you say about its competitiveness coefficient?

---

13.3

Show that the LFU algorithm does not achieve a bounded competitiveness coefficient.

---

13.4

Due to A. Bar-Noy, R. Motwani, and J. Naor [45].

Given an undirected graph $G(V,E)$, an edge coloring is an assignment of indices $1,\dots ,C$ to the edges of $G$ such that no two edges incident on a vertex have the same label. The indices are referred to as colors, and the smallest value of $C$ for which such a coloring can be achieved is called the chromatic index of the graph. Vizing’s Theorem states that a graph with maximum degree $\Delta$ has chromatic index either $\Delta$ or $\Delta +1$; moreover, while distinguishing these two cases is an NP-hard problem, there is a polynomial time algorithm for coloring any graph with $\Delta +1$ colors. Consider the problem of online edge coloring: suppose that the edges of a graph with maximum degree $\Delta$ are presented one by one, and as each edge is specified it must be irrevocably assigned a color.

(a) Devise a deterministic online algorithm that uses at most $2\Delta -1$ colors.

(b) Show that there does not exist any deterministic algorithm that uses fewer than $2\Delta -1$ colors in the worst case. For what range of values of $\Delta$ can you prove this result? (Hint: Consider an adversary that generates a sequence of edges that constitute a graph composed of disjoint stars, where each star consists of a center vertex $v$ with $\Delta -1$ neighbors of degree $1$. Once the algorithm has committed to a coloring of these stars, an adversary can introduce further edges from a distinguished vertex to the centers of appropriately chosen stars, forcing the online algorithm to use a large number of additional colors.)

(c) Show that there does not exist any deterministic algorithm that uses fewer than $2\Delta -1$ colors in the worst case. For what range of values of $\Delta$ can you prove this result? (Hint: See the hint for part (b).)

---

13.5

Due to A.R. Karlin.

Show that the competitiveness coefficient of the Random algorithm for paging against adaptive offline adversaries is at least $k{H}_k$.

---

13.6

Show that the competitiveness coefficient of the Random algorithm for paging against oblivious adversaries is at least $k$.

---

13.7

Show that when the number of distinct items in memory is $k+1$, the Marker algorithm is $H_k$-competitive.

---

13.8

Consider a server problem in which the online algorithm has $K$ servers, and the offline algorithm has $k$ servers. For $K\ge k$, show that the competitiveness coefficient of any online algorithm against adaptive online adversaries is at least $K/(K-k+1)$.

---

13.9

Consider the following algorithm for the $2$-server problem in an arbitrary metric space. Label the servers $0$ and $1$. The algorithm services any request as follows. Let $d_0$ be the distance from server $0$ to the request, and $d_1$ the distance from server $1$ to the request. Let $d$ be the distance between the servers. For $i\in \{0,1\}$, let

$$p_i=\frac{d+d_{1-i}-d_i}{2d}.$$

Server $i$ is used to select the request with probability $p_i$. Show that this algorithm is $2$-competitive against adaptive online adversaries.

---

13.10

Due to R.M. Karp and P. Raghavan.

Show that the competitiveness coefficient of any randomized online algorithm for maintaining a linear list against an oblivious adversary is at least $9/8$. (Hint: Consider a list with $2$ items.)

---

13.11

Consider the Reciprocal algorithm for weighted paging, in the scenario of Problem 13.8: Reciprocal manages a cache with $K$ pages, while the adversary has $k$ pages. Show that Reciprocal achieves a competitiveness coefficient of $K/(K-k+1)$, matching the lower bound of Problem 13.8.

---

13.12

Due to S.S. Irani [207].

Consider the list update problem again, with the following modification in the cost function: the cost of accessing the item at the $i$th position in the list is $i-1$, rather than $i$ (thus the item at the head of the list is accessed at cost zero). For lists with two items, show that $3/2$ is a tight bound on the competitiveness coefficient of randomized algorithms against oblivious adversaries, under this cost function.

---

13.13

Give a metric space for which you can prove a lower bound of $k(k+1)/2$ on the competitiveness coefficient of the Harmonic algorithm against an adaptive online adversary. (Hint: Make use of the result of Problem 6.7.)