Work-Function Algorithm for k Servers
- PDF / 212,692 Bytes
- 2 Pages / 547.087 x 737.008 pts Page_size
- 0 Downloads / 188 Views
W
14. Mo, Y.-Y., Chu, C.: A hybrid dynamic/quadratic programming algorithm for interconnect tree optimization. IEEE Trans. Comput. Des. 20(5), 680–686 (2001) 15. Sapatnekar, S.S.: RC interconnect optimization under the Elmore delay model. In: Proc. ACM/IEEE Design Automation Conf., pp. 387–391. ACM, New York (1994)
Work-Function Algorithm for k Servers 1994; Koutsoupias, Papadimitriou MAREK CHROBAK Department of Computer Science at Riverside, University of California at Riverside, Riverside, CA, USA Problem Definition In the k-server problem, the task is to schedule the movement of k servers in a metric space M in response to a sequence % = r1 ; r2 ; : : : ; r n of requests, where r i 2 M for all i. The servers initially occupy some configuration X 0 M. After each request ri is issued, one of the k servers must move to ri . A schedule S specifies which server moves to each request. The task is to compute a schedule with minimum cost, where the cost of a schedule is defined as the total distance traveled by the servers. The example below shows a schedule for 2 servers on a sequence of requests. In the offline case, given M, X 0 , and the complete request sequence %, the optimal schedule can be computed in polynomial time [6]. In the online version of the problem the decision as to which server to move to each request ri must be made before the next request r i+1 is issued. It is quite easy to see that in this online scenario it is not possible to guarantee an optimal schedule. The accuracy of online algorithms is often measured using competitive analysis. Denote by costA (%) the cost of the schedule produced by an online kserver algorithm A on a request sequence %, and let opt(%) be the cost of an optimal schedule on %. A is called Rcompetitive if costA (%) R opt(%) + B, where B is a constant that may depend on M and X 0 . The smallest such R is called the competitive ratio of A. Of course, the smaller the R the better. The k-server problem was introduced by Manasse, McGeoch, and Sleator [13,14], who proved that no (deterministic) on-line algorithm can achieve a competitive ratio smaller than k, in any metric space with at least k + 1 points. They also gave a 2-competitive algorithm for k = 2 and stated what is now known as the k-server conjecture,
Work-Function Algorithm for k Servers, Figure 1 A schedule for 2 servers on a request sequence % = r1 ; r2 ; : : : ; r7 . The initial configuration is X0 = fx1 ; x2 g. Server 1 serves r1 ; r2 ; r5 ; r6 , while server 2 serves r3 ; r4 ; r7 . The cost of this schedule is d(x1 ; r1 ) + d(r1 ; r2 ) + d(r2 ; r5 ) + d(r5 ; r6 ) + d(x2 ; r3 ) + d(r3 ; r4 ) + d(r4 ; r7 ), where d(x, y) denotes the distance between points x, y
which postulates that there exists a k-competitive online algorithm for all k. Koutsoupias and Papadimitriou [10,11] (see also [3,8,9]) proved that the work-function algorithm presented in the next section has competitive ratio at most 2k 1, which to date remains the best upper bound known. Key Results The idea of the work-function algorithm is to balan
Data Loading...
