Academic
Publications
Competitive Algorithms for Server Problems

Competitive Algorithms for Server Problems,10.1016/0196-6774(90)90003-W,Journal of Algorithms,Mark S. Manasse,Lyle A. Mcgeoch,Daniel Dominic Sleator

Competitive Algorithms for Server Problems   (Citations: 231)
BibTex | RIS | RefWorks Download
on-line algorithms for this problem from the competitive point of view. That is, we seek to develop on-line algorithms whose performance on any sequence of requests is as close as possible to the performance of the optimum off-line algorithm. We obtain optimally competitive algorithms for several important cases. Because of the flexibility in choosing the distances in the graph and the number of servers, the k-server problem can be used to model a number of important paging and caching problems. It can also be used as a building block for solving more general problems. We show how server algorithms can be used to solve a seemingly more general class
Journal: Journal of Algorithms - JAL , vol. 11, no. 2, pp. 208-230, 1990
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...The k-server problem in its full generality was first posed by Manasse et al. [16]...

    Nikhil Bansalet al. Towards the Randomized k-Server Conjecture: A Primal-Dual Approach

    • ...The objective then is to place the at most k servers so as to minimize the sum of distances of demand points to their nearest servers, over some period of time [15]...

    Matt Gibsonet al. On Metric Clustering to Minimize the Sum of Radii

    • ...The k-server problem on an n-state metric [2], for example, can be modeled as a metrical task system problem with � n � states 1 Another example is...

    Jacob Abernethyet al. A Regularization Approach to Metrical Task Systems

    • ...In the k-server problem [11] one has to decide how k mobile servers should serve a sequence of requests appearing at various locations of a metric space with altogether m locations...
    • ...Thus with lack of practical evidence, it is not quite clear whether the competitive but complex WFA can really provide better service than much simpler but noncompetitive heuristics [6,11]...
    • ...Another heuristic is the balanced algorithm (BALANCE) [11], which attempts to keep distances moved by various servers roughly equal, thus employing the server whose cumulative distance traveled so far plus the distance to the requested location is minimal...
    • ...It can easily be proved [11] that any αcompetitive algorithm for the k-server problem must have α ≥ k. Also, it is easy to check [6] that RAND, GREEDY and BALANCE are not competitive...
    • ...if the locations form a line [1,3], if all but two locations are covered by servers [9], or if there are exactly two servers [11]...

    Tomislav Rudecet al. Measuring True Performance of the Work Function Algorithm for Solving ...

    • ...ZA under the strategy A, if there exists a constant r can ensure the formula ZA(R) • rZs(R) for all the demands R, the efficiency loss of the strategy A is r, the smaller the efficiency loss r, the better the strategy A [8], [9]...

    Xiaoping Wuet al. The Efficiency Loss of User Equilibrium with Linear Nonseparable and A...

Sort by: