ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
The harmonic online K-server algorithm is competitive
Full text PdfPdf (533 KB)
Source Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-third annual ACM symposium on Theory of computing table of contents
New Orleans, Louisiana, United States
Pages: 260 - 266  
Year of Publication: 1991
ISBN:0-89791-397-3
Author
E. F. Grove  Univ. of California, Berkeley
Sponsor
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 2,   Downloads (12 Months): 14,   Citation Count: 7
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/103418.103448
What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

BBKTW90
S. Ben-David , A. Borodin , R. Karp , G. Tardos , A. Wigderson, On the power of randomization in online algorithms, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.379-386, May 13-17, 1990, Baltimore, Maryland, United States  [doi>10.1145/100216.100268]
 
BKT90
P. Berman , H. Karloff , G. Tardos, A competitive 3-server algorithm, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.280-290, January 22-24, 1990, San Francisco, California, United States
 
C90
M. Chrobak, personal correspondence to E. Grove.
 
CKPV90
M. Chrobak , H. Karloff , T. Payne , S. Vishwanathan, New results on server problems, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.291-300, January 22-24, 1990, San Francisco, California, United States
 
FRR90
Amos Fiat, Yuval Rabani, and Yiftach Ravid. "Competitive k-Server Algorithms." Proceedings 31st Annual Symposium on Foundations of Computer Science Volume II, pages 454-469, October 1990.
MMS88
Mark Manasse , Lyle McGeoch , Daniel Sleator, Competitive algorithms for on-line problems, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.322-333, May 02-04, 1988, Chicago, Illinois, United States  [doi>10.1145/62212.62243]
 
RS89
Prabhakar Raghavan , Marc Snir, Memory Versus Randomization in On-line Algorithms (Extended Abstract), Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.687-703, July 11-15, 1989
ST85
Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985  [doi>10.1145/2786.2793]

CITED BY  7
Allan Borodin , Nathan Linial , Michael E. Saks, An optimal on-line algorithm for metrical task system, Journal of the ACM (JACM), v.39 n.4, p.745-763, Oct. 1992
Prasad Tetali, Design of on-line algorithms using hitting times, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.402-411, January 23-25, 1994, Arlington, Virginia, United States
Don Coppersmith , Peter Doyle , Prabhakar Raghavan , Marc Snir, Random walks on weighted graphs and applications to on-line algorithms, Journal of the ACM (JACM), v.40 n.3, p.421-453, July 1993
Elias Koutsoupias , Christos H. Papadimitriou, On the k-server conjecture, Journal of the ACM (JACM), v.42 n.5, p.971-983, Sept. 1995
Yair Bartal , Eddie Grove, The harmonic k-server algorithm is competitive, Journal of the ACM (JACM), v.47 n.1, p.1-15, Jan. 2000
Elias Koutsoupias , David Scot Taylor, The CNN problem and other k-server variants, Theoretical Computer Science, v.324 n.2-3, p.347-359, 20 September 2004
William F. Klostermeyer , Kankanahalli Srinivas, Reducing disk power consumption in a portable computer, ACM SIGOPS Operating Systems Review, v.29 n.2, p.27-32, April 1995

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling


General Terms:
Algorithms, Measurement, Performance, Theory

Collaborative Colleagues:
E. F. Grove: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player