Trackless Servers: Lesson IV. Updating the Trackless Workfunction.

Back to Table of Contents

Previous Lesson

Next Lesson


We walk through the process of updating the trackless workfunction, starting with the example on the left.

Trackless Workfunction tau = 2.1.212101. Potential = 4
dist
to
s 		2
1 0
1 2 1 1
0
2

0 1 2
dist to r

The Request. Let tau be the trackless workfunction. The adversary selects a request point r'. Because of the trackless restriction, all the algorithm is told is the values of e = rr' and f = sr', that is, that r' maps to (a,b). In our example, we let e = 1 and f = 2.

We now define a new function upsilon on D, where upsilon(x,y) is the minimum of tau(x,y)+e and tau(e,f)+x. We use the notation upsilon = tau_(e,f). The value upsilon(x,y) is a lower bound on the value of w'(p), where p is any point which maps to (x,y) under the projection P, that is, pr = x and ps = y.

Function upsilon = tau_(1,2)
dist
to
s 		2
2 1
1 1 2 2
0
2

0 1 2
dist to r

Offset. We let A be the maximum allowed value of the offset. The optimal algorithm makes an offset payment of A. The new function is zeta = upsilon - A. In the example, A = 1.

The algorithms's servers are still at r and at s, but one of them must move to r'. The image of r' in the diagram is colored light red.

Function zeta = upsilon - 1, after offset payment
dist
to
s 		2
1 0
1 0 1 1
0
1

0 1 2
dist to r

Suppose the algorithm moves its server from r to r'. Then, (x,y) represents all points of distance x to r' and distance y to s. Let p be such a point. We need to estimate pr. After careful calculation, it is possible to prove that |a-x| and |b-y| are both lower bounds for pr, while a+x, b+y, and, of course, N, are upper bounds.

Let zeta_r be the new trackless workfunction if the algorithm servers the request by moving from r. Then zeta_r(x,y) = min zeta(z,y) where the minimum is taken over all z in the range max{|a-x|,|b-y|}...min{a+x,b+y,N}. The algorithm cost for this move is rr'.

Here on the left is the new trackless workfunction in our example. Recall that what is now called r is what previously was called r'.

After serving with r, the new function is zeta_r = Trackless Workfunction 2.2.010011. Potential = 4
dist
to
s 		2 1 0 0
1
0 1
0

1

0 1 2
dist to r

On the other had, if the algorithm serves by moving its server from s to r', the new trackless work function, zeta_s, must be defined in terms of distances to r' and s' = r. The theoretical situation is identical to the previous case. We picture the resulting trackless workfunction, in our example, below.

Exercise 4.1. Write, in closed form, the formula for zeta_s(x,y), just as was done for zeta_r above. Answer

In the table below, recall that what is now called r is what previously was called r', and what is now called s is what previously was called r.

h_s = Trackless Workfunction 2.1.110001. This will be the new function if the request is served by s. Potential = 4
dist
to
s 		2
0 0
1 1 1 1
0
0

0 1 2
dist to r


Next Lesson