{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T15:10:28Z","timestamp":1736953828872,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":56,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540667315"},{"type":"electronic","value":"9783540467847"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-46784-x_2","type":"book-chapter","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T12:02:55Z","timestamp":1175774575000},"page":"10-26","source":"Crossref","is-referenced-by-count":6,"title":["Online Algorithms: A Study of Graph-Theoretic Concepts"],"prefix":"10.1007","author":[{"given":"Susanne","family":"Albers","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1137\/S0097539794277858","volume":"27","author":"S. Albers","year":"1998","unstructured":"S. Albers. Improved randomized on-line algorithms for the list update problem. SIAM Journal on Computing, 27:670\u2013681, 1998. 17","journal-title":"SIAM Journal on Computing"},{"unstructured":"S. Albers, S. Arora and S. Khanna. Page replacement for general caching problems. Proc. 10th Annual ACM-SIAM Symp. on Discrete Algorithms, 31\u201340, 1999. 15","key":"2_CR2"},{"doi-asserted-by":"crossref","unstructured":"S. Albers and M. Henzinger. Exploring unknown environments. Proc. 29th Annual ACM Symposium on Theory of Computing, 416\u2013425, 1997. 18, 21","key":"2_CR3","DOI":"10.1145\/258533.258630"},{"key":"2_CR4","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1006\/jagm.1997.0906","volume":"27","author":"S. Albers","year":"1998","unstructured":"S. Albers and H. Koga. New on-line algorithms for the page replication problem. Journal of Algorithms, 27:75\u201396, 1998. 22","journal-title":"Journal of Algorithms"},{"unstructured":"S. Albers and K. Kursawe.Exploring unknown environments with obstacles. Proc. 10th Annual ACM-SIAM Symp. on Discrete Algorithms, 842\u2013843, 1999. 18, 19, 20","key":"2_CR5"},{"key":"2_CR6","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/PL00009217","volume":"21","author":"S. Albers","year":"1998","unstructured":"S. Albers and M. Mitzenmacher. Average case analyses of list update algorithms, with applications to data compression. Algorithmica, 21:312\u2013329, 1998. 16, 17","journal-title":"Algorithmica"},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0020-0190(95)00142-Y","volume":"56","author":"S. Albers","year":"1995","unstructured":"S. Albers, B. von Stengel and R. Werchner. A combined BIT and TIMESTAMP algorithm for the list update problem. Information Processing Letters, 56:135\u2013139, 1995. 17, 18","journal-title":"Information Processing Letters"},{"unstructured":"C. Amb\u00fchl, B. G\u00e4rtner and B. von Stengel. Towards new lower bounds for the list update problem.T o appear in Theoretical Computer Science. 18","key":"2_CR8"},{"doi-asserted-by":"crossref","unstructured":"J. Aspnes, Y. Azar A. Fiat, S. Plotkin and O. Waarts. On-line load balancing with applications to machine scheduling and virtual circuit routing. Proc. 25th ACM Annual ACM Symp. on the Theory of Computing, 623\u2013631, 1993. 23","key":"2_CR9","DOI":"10.1145\/167088.167248"},{"unstructured":"B. Awerbuch, Y. Azar and. Y. Bartal. On-line generalized Steiner tree problem. Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, 68\u201374, 1996. 24","key":"2_CR10"},{"doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Y. Azar and S. Plotkin. Throughput-competitive online routing. 34th IEEE Symp. on Foundations of Computer Science, 32\u201340, 1993. 23, 24","key":"2_CR11","DOI":"10.1109\/SFCS.1993.366884"},{"doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Y. Bartal and A. Fiat. Competitive distributed file allocation. Proc. 25th Annual ACM Symp. on Theory of Computing, 164\u2013173, 1993. 22","key":"2_CR12","DOI":"10.1145\/167088.167142"},{"doi-asserted-by":"crossref","unstructured":"B. Awerbuch, M. Betke, R. Rivest and M. Singh. Piecemeal graph learning by a mobile robot. Proc. 8th Conference on Computational Learning Theory, 321\u2013328, 1995. 18, 20","key":"2_CR13","DOI":"10.1145\/225298.225337"},{"unstructured":"Y. Bartal, M. Charikar and P. Indyk. On page migration and other relaxed task systems. Proc. of the 8th Annual ACM-SIAM Symp. on Discrete Algorithms, 43\u201352, 1997. 22","key":"2_CR14"},{"doi-asserted-by":"crossref","unstructured":"Y. Bartal, A. Fiat and Y. Rabani. Competitive algorithms for distributed data management. Proc. 24th Annual ACM Symp. on Theory of Computing, 39\u201350, 1992. 22","key":"2_CR15","DOI":"10.1145\/129712.129717"},{"key":"2_CR16","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1147\/sj.52.0078","volume":"5","author":"L.A. Belady","year":"1966","unstructured":"L.A. Belady. A study of replacement algorithms for virtual storage computers. IBM Systems Journal, 5:78\u2013101, 1966. 11","journal-title":"IBM Systems Journal"},{"key":"2_CR17","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.M. Karp, G. Tardos and A. Wigderson. On the power of randomization in on-line algorithms. Algorithmica, 11:2\u201314,1994. 17","journal-title":"Algorithmica"},{"unstructured":"J.L. Bentley, K.L. Clarkson and D.B. Levine. Fast linear expected-time algorithms for computing maxima and convex hulls. Proc. of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, 179\u2013187, 1990. 16","key":"2_CR18"},{"key":"2_CR19","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1145\/3341.3349","volume":"28","author":"J.L. Bentley","year":"1985","unstructured":"J.L. Bentley and C.C. McGeoch. A mortized analyses of self-organizing sequential search heuristics. Communication of the ACM, 28:404\u2013411, 1985. 16","journal-title":"Communication of the ACM"},{"key":"2_CR20","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1145\/5684.5688","volume":"29","author":"J.L. Bentley","year":"1986","unstructured":"J.L. Bentley, D.S. Sleator, R.E. Tarjan and V.K. Wei. A locally adaptive data compression scheme. Communication of the ACM, 29:320\u2013330, 1986. 16","journal-title":"Communication of the ACM"},{"doi-asserted-by":"crossref","unstructured":"P. Berman and C. Coulston. Online algorithms for Steiner tree problems. Proc. 29th Annual ACM Symposium on Theory of Computing, 344\u2013353, 1997. 24","key":"2_CR21","DOI":"10.1145\/258533.258618"},{"doi-asserted-by":"crossref","unstructured":"M. Betke, R. Rivest and M. Singh. Piecemeal learning of an unknown environment. Proc. 5th Conference on Computational Learning Theory, 277\u2013286, 1993. 18, 19","key":"2_CR22","DOI":"10.1145\/168304.168352"},{"unstructured":"D.L. Black and D.D. Sleator. Competitive algorithms for replication and migration problems.Technical Report Carnegie Mellon University, CMU-CS-89-201, 1989. 22","key":"2_CR23"},{"unstructured":"M. Burrows and D.J. Wheeler. A block-sorting lossless data compression algorithm. DEC SRC Research Report 124, 1994. 16","key":"2_CR24"},{"key":"2_CR25","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1137\/0404017","volume":"4","author":"M. Chrobak","year":"1991","unstructured":"M. Chrobak, H. Karloff, T. Paye and S. Vishwanathan. New results on the server problem. SIAM Journal on Discrete Mathematics, 4:172\u2013181, 1991. 14","journal-title":"SIAM Journal on Discrete Mathematics"},{"unstructured":"M. Chrobak and J. Noga. LRU is better than FIFO. Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 78\u201381, 1998. 13","key":"2_CR26"},{"key":"2_CR27","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1006\/jcss.1995.1021","volume":"50","author":"A. Borodin","year":"1995","unstructured":"A. Borodin, S. Irani, P. Raghavan and B. Schieber. Competitive paging with locality of reference. Journal on Computer and System Sciences, 50:244\u2013258, 1995. 12, 13","journal-title":"Journal on Computer and System Sciences"},{"key":"2_CR28","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/274787.274788","volume":"45","author":"X. Deng","year":"1998","unstructured":"X. Deng, T. Kameda and C. H. Papadimitriou. How to learn an unknown environment. Journal of the ACM, 45:215\u2013245, 1998. 18","journal-title":"Journal of the ACM"},{"doi-asserted-by":"crossref","unstructured":"X. Deng and C.H. Papadimitriou. Exploring an unknown graph. Proc. 31st Symposium on Foundations of Computer Science, 356\u2013361, 1990. 18, 20","key":"2_CR29","DOI":"10.1109\/FSCS.1990.89554"},{"doi-asserted-by":"crossref","unstructured":"A. Fiat and A. Karlin. Randomized and multipointer paging with locality of reference. Proc. 27th Annual ACM Symposium on Theory of Compting, 626\u2013634, 1995. 13","key":"2_CR30","DOI":"10.1145\/225058.225280"},{"unstructured":"A. Fiat and Z. Rosen. Experimental studies of access graph based heuristics: Beating the LRU standard. Proc. 8th Annual ACM-SIAM Symp. on Discrete Algorithms, 63\u201372, 1997. 13","key":"2_CR31"},{"unstructured":"M.J. Golin. PhD thesis, Department of Computer Science, Princeton University, 1990.Technical Report CS-TR-266-90. 16","key":"2_CR32"},{"unstructured":"F. Hoffmann, C. Icking, R. Klein and K. Kriegel. A competitive strategy for learning a polygon. Proc. 8th ACM-SIAM Symposium on Discrete Algorithms, 166\u2013174, 1997. 18","key":"2_CR33"},{"unstructured":"F. Hoffmann, C. Icking, R. Klein and K. Kriegel. The polygon exploration problem: A new strategy and a new analysis technique. Proc. 3rd International Workshop on Algorithmic Foundations of Robotics, 1998. 18","key":"2_CR34"},{"key":"2_CR35","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0020-0190(91)90086-W","volume":"38","author":"S. Irani","year":"1991","unstructured":"S. Irani. Two results on the list update problem. Information Processing Letters, 38:301\u2013306, 1991. 17","journal-title":"Information Processing Letters"},{"unstructured":"S. Irani. Corrected version of the SPLIT algorithm. Manuscript, January 1996. 17","key":"2_CR36"},{"issue":"1","key":"2_CR37","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF01294263","volume":"11","author":"S. Irani","year":"1994","unstructured":"S. Irani. Coloring inductive graphs on-line. Algorithmica, 11(1):53\u201362, 1994. 24","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"S. Irani. Page replacement with multi-size pages and applications to Web caching. Proc. 29th Annual ACM Symp. on Theory of Computing, 701\u2013710, 1997. 14","key":"2_CR38","DOI":"10.1145\/258533.258666"},{"unstructured":"S. Irani, A.R. Karlin and S. Phillips. Strongly competitive algorithms for paging with locality of reference. Proc. 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, 228\u2013236, 1992. 13","key":"2_CR39"},{"key":"2_CR40","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1137\/0404033","volume":"4","author":"M. Imase","year":"1991","unstructured":"M. Imase and B.M. Waxman. Dynamic Steiner tree problems. SIAM Journal on Discrete Mathematics, 4:349\u2013384, 1991. 24","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"2_CR41","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1006\/jagm.1993.1026","volume":"14","author":"B. Kalyanasundaram","year":"1993","unstructured":"B. Kalyanasundaram and K. Pruhs. Online wieghted matching. Journal of Algorithms, 14:139\u2013155, 1993. 24","journal-title":"Journal of Algorithms"},{"unstructured":"R. Karp and P. Raghavan. From a personal communication cited in [49]. 17","key":"2_CR42"},{"doi-asserted-by":"crossref","unstructured":"S. Khuller, S.G. Mitchell and V.V. Vazirani. On-line weighted bipartite matching. Proc. 18th International Colloquium on Automata, Languages and Programming (ICALP), Springer LNCS, Vol.510, 728\u2013738, 1991. 24","key":"2_CR43","DOI":"10.1007\/3-540-54233-7_178"},{"doi-asserted-by":"crossref","unstructured":"R. Karp, U. Vazirani and V. Vazirani. An optimal algorithm for online bipartite matching. Proc. 22nd ACM Symp. on Theory of Computing, 352\u2013358, 1990. 24","key":"2_CR44","DOI":"10.1145\/100216.100262"},{"key":"2_CR45","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1137\/0401048","volume":"1","author":"H.A. Kierstead","year":"1988","unstructured":"H.A. Kierstead. The linearity of First-Fit coloring of interval graphs. SIAM Journal on Discrete Mathematics, 1:526\u2013530, 1988. 24","journal-title":"SIAM Journal on Discrete Mathematics"},{"unstructured":"J. Kleinberg. On-line search in a simple polygon. Proc. 5th Annual ACM-SIAM Symposium on Discrete Algorithms, 8\u201315, 1994. 18, 20","key":"2_CR46"},{"doi-asserted-by":"crossref","unstructured":"S. Leonardi. On-line network routing. Online Algorithms: The State of the Art, Edited by A. Fiat and G. Woeginger, Springer LNCS, Volume 1442, 242\u2013267, 1998. 23","key":"2_CR47","DOI":"10.1007\/BFb0029572"},{"key":"2_CR48","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0012-365X(89)90096-4","volume":"75","author":"L. Lovasz","year":"1989","unstructured":"L. Lovasz, M. Saks and M. Trotter. An online graph coloring algorithm with sublinear performance ratio. Discrete Mathematics, 75:319\u2013325, 1989. 24","journal-title":"Discrete Mathematics"},{"key":"2_CR49","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BF01294261","volume":"11","author":"N. Reingold","year":"1994","unstructured":"N. Reingold, J. Westbrook and D.D. Sleator. Randomized competitive algorithms for the list update problem. Algorithmica, 11:15\u201332, 1994. 17, 26","journal-title":"Algorithmica"},{"key":"2_CR50","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:202\u2013208, 1985. 10, 11, 12, 16","journal-title":"Communications of the ACM"},{"key":"2_CR51","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/0020-0190(93)90150-8","volume":"47","author":"B. Teia","year":"1993","unstructured":"B. Teia. A lower bound for randomized list update algorithms. Information Processing Letters, 47:5\u20139, 1993. 18","journal-title":"Information Processing Letters"},{"key":"2_CR52","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1016\/0196-6774(92)90061-G","volume":"13","author":"S. Vishwanathan","year":"1992","unstructured":"S. Vishwanathan. Randomized online graph coloring. Journal of Algorithms, 13:657\u2013669, 1992. 24","journal-title":"Journal of Algorithms"},{"key":"2_CR53","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/BF01189992","volume":"11","author":"N. Young","year":"1994","unstructured":"N. Young. The k-server dual and loose competitiveness for paging. Algorithmica, 11:525\u2013541, 1994. 12","journal-title":"Algorithmica"},{"unstructured":"N.E. Young. Online file caching. Proc. 9th Annual ACM-SIAM Symp. on Discrete Algorithms, 82\u201386, 1998. 14","key":"2_CR54"},{"key":"2_CR55","doi-asserted-by":"publisher","first-page":"951","DOI":"10.1137\/S0097539791199796","volume":"23","author":"J. Westbrook","year":"1994","unstructured":"J. Westbrook. Randomized algorithms for the multiprocessor page migration. SIAM Journal on Computing, 23:951\u2013965, 1994. 22","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"J. Westbrook and D.C. Yan. Lazy and greedy: On-line algorithms for Steiner problems. Proc. Workshop on Algorithms and Data Structures, Springer LNCS Volume 709, 622\u2013633, 1993. 24","key":"2_CR56","DOI":"10.1007\/3-540-57155-8_285"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46784-X_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T14:32:52Z","timestamp":1736951572000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46784-X_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540667315","9783540467847"],"references-count":56,"URL":"https:\/\/doi.org\/10.1007\/3-540-46784-x_2","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}