Cited By
View all- Chrobak M(2006)2005ACM SIGACT News10.1145/1122480.112249937:1(82-98)Online publication date: 1-Mar-2006
The delayed k-server problem
Pages 281 - 292
Abstract
We introduce a new version of the server problem: the delayed server problem. In this problem, once a server moves to serve a request, it must wait for one round to move again, but could serve a repeated request to the same point. We show that the delayed k-server problem is equivalent to the (k–1)-server problem in the uniform case, but not in general.
References
[1]
Wolfgang Bein, Marek Chrobak, and Lawrence L. Larmore. The 3-server problem in the plane. Theoretical Computer Science, 287(1):387-391, 2002.
[2]
Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
[3]
William R. Burley. Traversing layered graphs using the work function algorithm. Journal of Algorithms, 20:479-511, 1996.
[4]
Marek Chrobak, Howard Karloff, Tom H. Payne, and Sundar Vishwanathan. New results on server problems. SIAM Journal on Discrete Mathematics, 4:172-181, 1991.
[5]
Marek Chrobak and Lawrence L. Larmore. An optimal online algorithm for k servers on trees. SIAM Journal on Computing, 20:144-148, 1991.
[6]
Marek Chrobak and Lawrence L. Larmore. Metrical task systems, the server problem, and the work function algorithm. In Amos Fiat and Gerhard J. Woeginger, editors, Online Algorithms: The State of the Art, pages 74-94. Springer, 1998.
[7]
Don Coppersmith, Peter G. Doyle, Prabhakar Raghavan, and Marc Snir. Random walks on weighted graphs and applications to online algorithms. In Proc. 22nd Symp. Theory of Computing (STOC), pages 369-378. ACM, 1990.
[8]
Elias Koutsoupias and Christos Papadimitriou. On the k-server conjecture. In Proc. 26th Symp. Theory of Computing (STOC), pages 507-511. ACM, 1994.
[9]
Elias Koutsoupias and Christos Papadimitriou. On the k-server conjecture. Journal of the ACM, 42:971-983, 1995.
[10]
Elias Koutsoupias and Christos Papadimitriou. The 2-evader problem. Information Processing Letters, 57:249-252, 1996.
[11]
Mark Manasse, Lyle A. McGeoch, and Daniel Sleator. Competitive algorithms for server problems. Journal of Algorithms, 11:208-230, 1990.
- The delayed k-server problem
Recommendations
On the online fault-tolerant server consolidation problem
SPAA '14: Proceedings of the 26th ACM symposium on Parallelism in algorithms and architecturesIn the server consolidation problem, the goal is to minimize the number of servers needed to host a set of clients. The clients appear in an online manner and each of them has a certain load. The servers have uniform capacity and the total load of ...
Improving web cache server performance through arbitral thread and delayed caching
As the number of Internet users increase explosively, the delay in network response time is also increasing. An economic and efficient solution for this problem is web caching. But the use of a cache server can cause another bottleneck because of the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 17 August 2005
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 15 Feb 2025
Other Metrics
Citations
Cited By
View all- Chrobak M(2006)2005ACM SIGACT News10.1145/1122480.112249937:1(82-98)Online publication date: 1-Mar-2006