9.2. 9.2 The -server problem

One of the best-known on-line problems is the on-line -server problem. To give the definition of the general problem the notion of metric spaces is needed. A pair (where contains the points of the space and is the distance function defined on the set ) is called metric space if the following properties are valid:

In the -server problem a metric space is given, and there are servers which can move in the space. The decision maker has to satisfy a list of requests appearing at the points of the metric space by sending a server to the point where the request appears.

The problem is on-line which means that the requests arrive one by one, and we must satisfy each request without any information about the further requests. The goal is to minimise the total distance travelled by the servers. In the remaining parts of the section the multiset which contains the points where the servers are is called the configuration of the servers. We use multisets, since different servers can be at the same points of the space.

The first important results for the -server problem were achieved by Manasse, McGeoch and Sleator. They developed the following algorithm called Balance , which we denote by BAL . During the procedure the servers are in different points. The algorithm stores for each server the total distance travelled by the server. The servers and the points in the space where the servers are located are denoted by . Let the total distance travelled by the server be . After the arrival of a request at point algorithm BAL uses server for which the value is minimal. This means that the algorithm tries to balance the distances travelled by the servers. Therefore the algorithm maintains server configuration and the distances travelled by the servers which distances have starting values . The behaviour of the algorithm on input can be given by the following pseudocode:

BAL( )

  1  
                     FOR
                   
                   
                  
                     TO
                   
                     2    
                     DO
                   
                     3       serve the request with server    4          5         
               

Example 9.1 Consider the two dimensional Euclidean space as the metric space. The points are two dimensional real vectors , and the distance between and is . Suppose that there are two servers which are located at points and at the beginning. Therefore at the beginning , , . Suppose that the first request appears at point . Then , thus the second server is used to satisfy the request and after the action of the server , , . Suppose that the second request appears at point , so , thus again the second server is used, and after serving the request , , . Suppose that the third request appears at point , so , thus the first server is used, and after serving the request , , .

The algorithm is efficient in the cases of some particular metric spaces as it is shown by the following statement. The references where the proof of the following theorem can be found are in the chapter notes at the end of the chapter.

Theorem 9.1 Algorithm Balance is weakly -competitive for the metric spaces containing points.

The following statement shows that there is no on-line algorithm which is better than -competitive for the general -server problem.

Theorem 9.2 There is no metric space containing at least points where an on-line algorithm exists with smaller competitive ratio than .

Proof. Consider an arbitrary metric space containing at least points and an arbitrary on-line algorithm say ONL . Denote the points of the starting configuration of ONL by , and let be another point of the metric space. Consider the following long list of requests . The next request appears at the point among where ONL has no server.

First calculate the value . The algorithm does not have any servers at point after serving , thus the request appeared at is served by the server located at point . Therefore the cost of serving is , which yields

where denotes the point from which the server was sent to serve . (This is the point where the -th request would appear.) Now consider the cost . Instead of calculating the optimal off-line cost we define different off-line algorithms, and we use the mean of the costs resulting from these algorithms. Since the cost of each off-line algorithm is at least as much as the optimal off-line cost, the calculated mean is an upper bound for the optimal off-line cost.

We define the following off-line algorithms, denoted by . Suppose that the servers are at points in the starting configuration of . We can move the servers into this starting configuration using an extra constant cost .

The algorithms satisfy the requests as follows. If an algorithm has a server at point , then none of the servers moves. Otherwise the request is served by the server located at point . The algorithms are well-defined, if does not contain a server, then each of the other points contains a server, thus there is a server located at . Moreover , thus at the beginning each algorithm has a server at the requested point.

We show that the servers of algorithms are always in different configurations. At the beginning this property is valid because of the definition of the algorithms. Now consider the step where a request is served. Call the algorithms which do not move a server for serving the request stable, and the other algorithms unstable. The server configurations of the stable algorithms remain unchanged, so these configurations remain different from each other. Each unstable algorithm moves a server from point . This point is the place of the last request, thus the stable algorithms have server at it. Therefore, an unstable algorithm and a stable algorithm cannot have the same configuration after serving the request. Furthermore, each unstable algorithms moves a server from to , thus the server configurations of the unstable algorithms remain different from each other.

So at the arrival of the request at point the servers of the algorithms are in different configurations. On the other hand, each configuration has a server at point , therefore there is only one configuration where there is no server located at point . Consequently, the cost of serving is for one of the algorithms and for the other algorithms.

Therefore

where is an absolute constant which is independent of the input (this is the cost of moving the servers to the starting configuration of the defined algorithms).

On the other hand, the optimal off-line cost cannot be larger than the cost of any of the above defined algorithms, thus . This yields

which inequality shows that the weak competitive ratio of ONL cannot be smaller than , since the value can be arbitrarily large as the length of the input is increasing.

There are many interesting results in connection with this problem.have appeared during the next few years. For the general case the first constant-competitive algorithm (-competitive) was developed by Fiat, Rabani and Ravid. Later Koutsoupias and Papadimitriou could analyse an algorithm based on the work function technique and they could prove that it is -competitive. They could not determine the competitive ratio of the algorithm, but it is a widely believed hypothesis that the algorithm is -competitive. Determining the competitive ratio of the algorithm, or developing a -competitive algorithm is still among the most important open problems in the area of on-line algorithms. We present the work function algorithm below.

Denote the starting configuration of the on-line servers by . Then after the -th request the work function value belonging to multiset is the minimal cost needed to serve the first requests starting at configuration and ending at configuration . This value is denoted by . The Work-Function algorithm is based on the above defined work function. Suppose that is the server configuration before the arrival of the -th request, and denote the place of the -th request by . The Work-Function algorithm uses server to serve the request for which the value is minimal, where denotes the point where the server is actually located.

Example 9.2 Consider the metric space containing three points , and with the distances , , . Suppose that we have two servers and the starting configuration is . In this case the starting work function values are , , , , , . Suppose that the first request appears at point . Then and , thus algorithm Work Function uses the server from point to serve the request.

The following statement is valid for the algorithm.

Theorem 9.3 The Work-Function algorithm is weakly -competitive.

Besides the general problem many particular cases have been investigated. If the distance of any pair of points is , then we obtain the on-line paging problem as a special case. Another well investigated metric space is the line. The points of the line are considered as real numbers, and the distance of points and is . In this special case a -competitive algorithm was developed by Chrobak and Larmore, which algorithm is called Double-Coverage . A request at point is served by server which is the closest to . Moreover, if there are servers also on the opposite side of , then the closest server among them moves distance into the direction of . Hereafter we denote the Double-Coverage algorithm by DC . The input of the algorithm is the list of requests which is a list of points (real numbers) denoted by and the starting configuration of the servers is denoted by which contains points (real numbers) too. The algorithm can be defined by the following pseudocode:

DC( )

  1  
                     FOR
                   
                   
                  
                     TO
                   
                     2    
                     DO
                   
                     3  
                     IF
                   
                   or    4    
                     THEN
                      ≤/tab/≥  the request is served by the -th server   5          6    
                     ELSE
                   
                  
                     IF
                   
                     7       
                     THEN
                   
                     8                 the request is served by the -th server    9            10            11       
                     ELSE
                   
                  
                     IF
                   
                    12          
                     THEN
                   
                    13        the request is served by the -th server   14               15              
               

Example 9.3 Suppose that there are three servers located at points . If the next request appears at point , then DC uses the closest server to serve the request. The locations of the other servers remain unchanged, the cost of serving the request is and the servers are at points . If the next request appears at point , then DC uses the closest server to serve the request, but there are servers on the opposite side of the request, thus also travels distance into the direction of . Therefore the cost of serving the request is and the servers will be at points .

The following statement, which can be proved by the potential function technique, is valid for algorithm DC . This technique is often used in the analysis of on-line algorithms.

Theorem 9.4 Algorithm DC is weakly -competitive on the line.

Proof. Consider an arbitrary sequence of requests and denote this input by . During the analysis of the procedure we suppose that one off-line optimal algorithm and DC are running parallel on the input. We also suppose that each request is served first by the off-line algorithm and then by the on-line algorithm. The servers of the on-line algorithm and also the positions of the servers (which are real numbers) are denoted by , and the servers of the optimal off-line algorithm and also the positions of the servers are denoted by . We suppose that for the positions and are always valid, this can be achieved by swapping the notations of the servers.

We prove the theorem by the potential function technique. The potential function assigns a value to the actual positions of the servers, so the on-line and off-line costs are compared using the changes of the potential function. Let us define the following potential function:

The following statements are valid for the potential function.

While OPT is serving a request the increase of the potential function is not more than times the distance travelled by the servers of OPT .

While DC is serving a request, the decrease of is at least as much as the cost of serving the request.

If the above properties are valid, then one can prove the theorem easily. In this case , where and are the final and the starting values of the potential function. Furthermore, is nonnegative, so we obtain that , which yields that the algorithms is weakly -competitive ( does not depend on the input sequence only on the starting position of the servers).

Now we prove the properties of the potential function.

First consider the case when one of the off-line servers travels distance . The first part of the potential function increases at most by . The second part does not change, thus we proved the first property of the potential function.

Consider the servers of DC . Suppose that the request appears at point . Since the request is first served by OPT , for some . The following two cases are distinguished depending on the positions of the on-line servers.

First suppose that the on-line servers are on the same side of . We can assume that the positions of the servers are not smaller than , since the other case is completely similar. In this case is the closest server and DC sends to and the other on-line servers do not move. Therefore the cost of DC is . In the first sum of the potential function only changes; it decreases by , thus the first part decreases by . The second sum is increasing; the increase is , thus the value of decreases by .

Assume that there are servers on both sides of ; suppose that the closest servers are and . We assume that is closer to , the other case is completely similar. In this case the cost of DC is . Consider the first sum of the potential function. The -th and the -th part are changing. Since for some , thus one of the -th and the -th parts decreases by and the increase of the other one is at most , thus the first sum does not increase. The change of the second sum of is

Thus we proved that the second property of the potential function is also valid in this case.

Exercises

9.2-1 Suppose that is a metric space. Prove that is also a metric space where .

9.2-2 Consider the greedy algorithm which serves each request by the server which is closest to the place of the request. Prove that the algorithm is not constant competitive for the line.

9.2-3 Prove that for arbitrary -element multisets and and for arbitrary the inequality is valid, where is the cost of the minimal matching of and , (the minimal cost needed to move the servers from configuration to configuration ).

9.2-4 Consider the line as a metric space. Suppose that the servers of the on-line algorithm are at points , and the servers of the off-line algorithm are at points . Calculate the value of the potential function used in the proof of Theorem 9.4. How does this potential function change, if the on-line server moves from point to point ?