{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:51:40Z","timestamp":1725486700310},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540679967"},{"type":"electronic","value":"9783540444367"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44436-x_15","type":"book-chapter","created":{"date-parts":[[2007,6,18]],"date-time":"2007-06-18T05:33:14Z","timestamp":1182144794000},"page":"144-154","source":"Crossref","is-referenced-by-count":9,"title":["New Results for Online Page Replication"],"prefix":"10.1007","author":[{"given":"Rudolf","family":"Fleischer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steve","family":"Seiden","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,3]]},"reference":[{"key":"15_CR1","series-title":"Lect Notes Comput Sci","first-page":"75","volume-title":"Journal of Algorithms","author":"S. Albers","year":"1998","unstructured":"S. Albers and H. Koga. New on-line algorithms for the page replication problem. Journal of Algorithms, 27(1):75\u201396, 1998. A preliminary version was published in Proceedings of the 4th Scandinavian Workshop on Algorithm Theory (SWAT\u201994). Springer Lecture Notes in Computer Science 824, pages 25\u201336, 1994."},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF02573969","volume":"10","author":"N. Alon","year":"1993","unstructured":"N. Alon and Y. Azar. On-line Steiner trees in the Euclidean plane. Discrete and Computational Geometry, 10:113\u2013121, 1993. A preliminary version was published in Proceedings of the 8th Annual Symposium on Computational Geometry (SoCG\u201992), pages 337\u2013343, 1992.","journal-title":"Discrete and Computational Geometry"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Y. Bartal, and A. Fiat. Competitive distributed file allocation. In Proceedings of the 25th ACM Symposium on the Theory of Computation (STOC\u201993), pages 164\u2013173, 1993.","DOI":"10.1145\/167088.167142"},{"key":"15_CR4","unstructured":"Y. Bartal. Probabilistic approximation of metric spaces andits algorithmic applications. In Proceedings of the 37th Symposium on Foundations of Computer Science (FOCS\u201996), pages 183\u2013193, 1996."},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"Y. Bartal. On approximating arbitrary metrics by tree metrics. In Proceedings of the 30th ACM Symposium on the Theory of Computation (STOC\u201998), pages 161\u2013168, 1998.","DOI":"10.1145\/276698.276725"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Y. Bartal, A. Blum, C. Burch, and A. Tomkins. A polylog(n)-competitive algorithm for metrical task systems. In Proceedings of the 29th ACM Symposium on the Theory of Computation (STOC\u201997), pages 711\u2013719, 1997.","DOI":"10.1145\/258533.258667"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"Y. Bartal, A. Fiat, and Y. Rabani. Competitive algorithms for distributed data management. In Proceedings of the 24th ACM Symposium on the Theory of Computation (STOC\u201992), pages 39\u201350, 1992.","DOI":"10.1145\/129712.129717"},{"issue":"1","key":"15_CR8","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01294260","volume":"11","author":"S. Ben-David","year":"1994","unstructured":"S. Ben-David, A. Borodin, R. Karp, G. Tardos, and A. Wigderson. On the power of randomization in on-line algorithms. Algorithmica, 11(1):2\u201314, 1994. A preliminary version was published in Proceedings of the 22nd ACM Symposium on Theory of Computation (STOC\u201990), pages 379\u2013386, 1990.","journal-title":"Algorithmica"},{"key":"15_CR9","unstructured":"D. L. Black and D.D. Sleator. Competitive algorithms for replication and migration problems. Technical Report CMU-CS-89-201, Carnegie Mellon University, 1989."},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"A. Blum and C. Burch. On-line learning andth e metrical task system problem. In Proceedings of the 10th Conference on Computational Learning Theory, pages 45\u201353, 1997.","DOI":"10.1145\/267460.267475"},{"key":"15_CR11","volume-title":"Online Computation and Competitive Analysis","author":"A. Borodin","year":"1998","unstructured":"A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, Cambridge, England, 1998"},{"key":"15_CR12","series-title":"Lect Notes Comput Sci","volume-title":"Online Algorithms \u2014 The State of the Art","year":"1998","unstructured":"A. Fiat und G. Woeginger, editors. Online Algorithms \u2014 The State of the Art. Springer Lecture Notes in Computer Science 1442. Springer-Verlag, Heidelberg, 1998."},{"key":"15_CR13","unstructured":"W. Glazek. On-line algorithms for page replication in rings. Presented at the ALCOM Workshop on On-line Algorithms, Aug 31-Sep 5, Udine, Italy, 1998."},{"key":"15_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/3-540-48340-3_25","volume-title":"Proceedings of the 24th International Symposium on the Mathematical Foundations of Computer Science (MFCS\u201999)","author":"W. Glazek","year":"1999","unstructured":"W. Glazek. Lower andupp er bounds for the problem of page replication in ring networks. In Proceedings of the 24th International Symposium on the Mathematical Foundations of Computer Science (MFCS\u201999). Springer Lecture Notes in Computer Science 1672, pages 273\u2013283, 1999."},{"issue":"3","key":"15_CR15","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1137\/0404033","volume":"4","author":"M. Imase","year":"1991","unstructured":"M. Imase and B.M. Waxman. Dynamic Steiner tree problem. SIAM Journal on Discrete Mathematics, 4(3):369\u2013384, 1991.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"S. Irani. Page placement with multi-size pages andap plications to web caching. In Proceedings of the 29th ACM Symposium on the Theory of Computation (STOC\u201997), pages 701\u2013710, 1997.","DOI":"10.1145\/258533.258666"},{"issue":"1","key":"15_CR17","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF01762111","volume":"3","author":"A. R. Karlin","year":"1988","unstructured":"A. R. Karlin, M. S. Manasse, L. Rudolph, and D. D. Sleator. Competitive snoopy caching. Algorithmica, 3(1):79\u2013119, 1988.","journal-title":"Algorithmica"},{"key":"15_CR18","unstructured":"R. M. Karp. A 2k-competitive algorithm for the circle. Unpublished manuscript, 1989."},{"key":"15_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1007\/3-540-57568-5_275","volume-title":"Proceedings of the 4th International Symposium on Algorithms and Computation (ISAAC\u201993)","author":"H. Koga","year":"1993","unstructured":"H. Koga. Randomized on-line algorithms for the page replication problem. In Proceedings of the 4th International Symposium on Algorithms and Computation (ISAAC\u201993). Springer Lecture Notes in Computer Science 762, pages 436\u2013445, 1993."},{"key":"15_CR20","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1007\/BFb0049409","volume-title":"Proceedings of the 2nd European Symposium on Algorithms (ESA\u201994)","author":"C. Lund","year":"1994","unstructured":"C. Lund, N. Reingold, J. Westbrook, and D. Yan. On-line distributed data management. In Proceedings of the 2nd European Symposium on Algorithms (ESA\u201994). Springer Lecture Notes in Computer Science 855, pages 202\u2013214, 1994."},{"key":"15_CR21","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69672-5","volume-title":"Data Structures and Algorithms 1: Sorting and Searching","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching. Springer-Verlag, Heidelberg, 1984."},{"issue":"2","key":"15_CR22","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1006\/inco.1998.2744","volume":"148","author":"S. S. Seiden","year":"1999","unstructured":"S. S. Seiden. Unfair problems and randomized algorithms for metrical task systems.Information and Computation, 148(2):219\u2013240, 1999.","journal-title":"Information and Computation"},{"issue":"2","key":"15_CR23","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D. D. Sleator","year":"1985","unstructured":"D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202\u2013208, 1985.","journal-title":"Communications of the ACM"},{"key":"15_CR24","volume-title":"Theory of Games and Economic Behavior","author":"J. Neumann von","year":"1944","unstructured":"J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior.Princeton University Press, Princeton, NJ, 1. edition, 1944.","edition":"1"},{"key":"15_CR25","doi-asserted-by":"crossref","unstructured":"A. C. Yao. Probabilistic computations: Toward a unified measure of complexity. In Proceedings of the 18th Symposium on Foundations of Computer Science (FOCS\u201977), pages 222\u2013227, 1977.","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Lecture Notes in Computer Science","Approximation Algorithms for Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44436-X_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T23:55:15Z","timestamp":1556495715000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44436-X_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679967","9783540444367"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-44436-x_15","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}