Wolfgang W. Bein / Lawrence L. Larmore: Trackless Servers: Lesson I

Lesson I. The 2-Server Problem and Work Functions

Consider the classic 2-server problem in a metric space M. As is customary in discussions of on-line problems, we shall frequently refer to the on-line algorithm in the first person plural, and to the optimal off-line algorithm as the adversary. Sometimes the adversary is also referred to as "she."
We have (that is, the online algorithm has) two servers in M. We may assume that one of them is at r, the point which was most recently requested, and the other is at some other point s.
Our two servers are initially at two given points, s_0 and r_0. The optimal (that is, adversary's) servers must begin at the same two points.
The adversary generates a sequence of requests, r_1, r_2, ... r_n in M. Simultaneously , the adversary must service the same sequence with its own servers, meaning that, at time t, the adversary must move one server to r_t, the other server where it was. In general, we do not know where the adversary's other server is, although, since we can assume that the adversary is lazy, we can assume that it is at s_0, or at r_i for some i < t.
We let s_t be the location of our other server after t requests. Thus, our two servers are at s_t and r_t. Note that either s_t = r_{t-1} or s_t = s_{t-1}. If t is understood from context, we will use the relative notation: r = r_t, s = s_t, r' = r_{t+1}, and s' = s_{t+1}.
Work Functions. If rho = r_1 r_2 ... r_n is a request sequence, the optimal cost of servicing rho is computed using dynamic programming. A work function is very simply the table of partial calculations of that optimal cost at time any time step.
We define the workfunction w_t at time t to be a real-valued function defined on M, such that, for any p in M, w_t(p) is the minimum cost for two servers starting at r_0 and s_0 to serve the request sequence r_1 ... r_t, ending with its two servers at r_t and p.
Updating the Work Function. We use the relative notation w = w_t, w' = w_{t+1}, if t is understood. The update , which derives from dynamic programming, computes w' from w.
Exercise 1.1: Prove that update is computed by the following formula: w'(x) = min{rr' + w(x), rx + w(r')}. Answer.
Exercise 1.2: Prove that the work function is 1-Lipschitz, meaning that if xy is the distance between points x and y, then w(x) is less than or equal to w(y) + xy. Answer.
Offsetting the Workfunction. It is clear that the values of the work function grow ever larger as t increases. In order to simplify calculations, we introduce the notion of offset , which means to lower the value of the work function by a constant.
Using offset, we maintain the invariant that the minimum value of the work function is always 0. After computing w' from w, we let A be the minimum value of w', then redefine w' to be w' - A. We call A the offset value.
Obviously, after offset, the values of the work function will no longer be the optimal costs. But if we keep a running total of the offset values, that total will equal the optimal cost at time n.
Furthermore, algorithms that depend on the work function, such as the classic the Work Function Algorithm (WFA) and its variants, are not effected by altering the work function by a constant.

Lesson I. The 2-Server Problem and Work Functions
Consider the classic 2-server problem in a metric space M. As is customary in discussions of on-line problems, we shall frequently refer to the on-line algorithm in the first person plural, and to the optimal off-line algorithm as the adversary. Sometimes the adversary is also referred to as "she." We have (that is, the online algorithm has) two servers in M. We may assume that one of them is at r, the point which was most recently requested, and the other is at some other point s. Our two servers are initially at two given points, s_0 and r_0. The optimal (that is, adversary's) servers must begin at the same two points. The adversary generates a sequence of requests, r_1, r_2, ... r_n in M. Simultaneously , the adversary must service the same sequence with its own servers, meaning that, at time t, the adversary must move one server to r_t, the other server where it was. In general, we do not know where the adversary's other server is, although, since we can assume that the adversary is lazy, we can assume that it is at s_0, or at r_i for some i < t. We let s_t be the location of our other server after t requests. Thus, our two servers are at s_t and r_t. Note that either s_t = r_{t-1} or s_t = s_{t-1}. If t is understood from context, we will use the relative notation: r = r_t, s = s_t, r' = r_{t+1}, and s' = s_{t+1}. Work Functions. If rho = r_1 r_2 ... r_n is a request sequence, the optimal cost of servicing rho is computed using dynamic programming. A work function is very simply the table of partial calculations of that optimal cost at time any time step. We define the workfunction w_t at time t to be a real-valued function defined on M, such that, for any p in M, w_t(p) is the minimum cost for two servers starting at r_0 and s_0 to serve the request sequence r_1 ... r_t, ending with its two servers at r_t and p. Updating the Work Function. We use the relative notation w = w_t, w' = w_{t+1}, if t is understood. The update , which derives from dynamic programming, computes w' from w. Exercise 1.1: Prove that update is computed by the following formula: w'(x) = min{rr' + w(x), rx + w(r')}. Answer. Exercise 1.2: Prove that the work function is 1-Lipschitz, meaning that if xy is the distance between points x and y, then w(x) is less than or equal to w(y) + xy. Answer. Offsetting the Workfunction. It is clear that the values of the work function grow ever larger as t increases. In order to simplify calculations, we introduce the notion of offset , which means to lower the value of the work function by a constant. Using offset, we maintain the invariant that the minimum value of the work function is always 0. After computing w' from w, we let A be the minimum value of w', then redefine w' to be w' - A. We call A the offset value. Obviously, after offset, the values of the work function will no longer be the optimal costs. But if we keep a running total of the offset values, that total will equal the optimal cost at time n. Furthermore, algorithms that depend on the work function, such as the classic the Work Function Algorithm (WFA) and its variants, are not effected by altering the work function by a constant.

Back to Table of Contents
Next Lesson