On-line algorithms for cache sharing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On-line algorithms for cache sharing

Full text

Pdf (840 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 422 - 430

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Marshall Bern
Daniel Greene
Arvind Raghunathan

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 15, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/167088.167205 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.

	1	D. Black and D. Sleator, Competitive Algorithms for Replication and Migration Problems. Technical Report CMU-CS-89-201, Carnegie-Mellon University, 1989.
	2	Allan Borodin , Prabhakar Raghavan , Sandy Irani , Baruch Schieber, Competitive paging with locality of reference, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.249-259, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103422]
	3	P. Denning, Working Sets Past and Present. IEEE Trans. Software Eng. SE-6, 1980, 64-84.
	4	F. Douglis, The compression cache: using online compression to extend physical memory. 1993 Winter USENIX Conference, 519-529.
	5	E. R. Fiala , D. H. Greene, Data compression with finite windows, Communications of the ACM, v.32 n.4, p.490-505, April 1989 [doi>10.1145/63334.63341]
	6	Amos Fiat , Richard M. Karp , Michael Luby , Lyle A. McGeoch , Daniel D. Sleator , Neal E. Young, Competitive paging algorithms, Journal of Algorithms, v.12 n.4, p.685-699, Dec. 1991 [doi>10.1016/0196-6774(91)90041-V]
	7	Anna R. Karlin , Mark S. Manasse , Lyle A. McGeoch , Susan Owicki, Competitive randomized algorithms for non-uniform problems, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.301-309, January 22-24, 1990, San Francisco, California, United States
	8	A. Karlin, M. Manasse, L. Rudolph, and D. Sleator, Competitive snoopy caching. Algorithmica 3 (1988), 79-119.
	9	E. Lawler, Combinatorial Optimization: Net. works and Matroids. Holt, Rinehart and Winston, 1976.
	10	Mark S. Manasse , Lyle A. McGeoch , Daniel D. Sleator, Competitive algorithms for server problems, Journal of Algorithms, v.11 n.2, p.208-230, Jun. 1990 [doi>10.1016/0196-6774(90)90003-W]
	11	M. Nelson , B. Welch , J. Ousterhout, Caching in the Sprite network file system, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.3-4, November 08-11, 1987, Austin, Texas, United States
	12	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	13	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]
	14	James A. Storer, Data compression: methods and theory, Computer Science Press, Inc., New York, NY, 1987
	15	M. Taunton, Compressed Executables: an Exercise in Thinking Small. 1991 Summer USENIX Conference, 385-403.
	16	M. Theimer and K. Petersen, Xerox PARC, personal communication, 1990.
	17	Stephen Wolfram, Mathematica: a system for doing mathematics by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
	18	Neal Young, On-line caching as cache size varies, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.241-250, January 28-30, 1991, San Francisco, California, United States

CITED BY 2

	M. J. Feeley , W. E. Morgan , E. P. Pighin , A. R. Karlin , H. M. Levy , C. A. Thekkath, Implementing global memory management in a workstation cluster, ACM SIGOPS Operating Systems Review, v.29 n.5, p.201-212, Dec. 3, 1995
	Mark Weiser, Some computer science issues in ubiquitous computing, Communications of the ACM, v.36 n.7, p.75-84, July 1993