{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T19:49:12Z","timestamp":1760384952571,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642029264"},{"type":"electronic","value":"9783642029271"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02927-1_36","type":"book-chapter","created":{"date-parts":[[2009,7,4]],"date-time":"2009-07-04T04:37:10Z","timestamp":1246682230000},"page":"427-438","source":"Crossref","is-referenced-by-count":26,"title":["Online Computation with Advice"],"prefix":"10.1007","author":[{"given":"Yuval","family":"Emek","sequence":"first","affiliation":[]},{"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[]},{"given":"Amos","family":"Korman","sequence":"additional","affiliation":[]},{"given":"Adi","family":"Ros\u00e9n","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1\u20132","key":"36_CR1","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/S0304-3975(97)00026-1","volume":"197","author":"S. Albers","year":"1998","unstructured":"Albers, S.: A competitive analysis of the list update problem with lookahead. Theor. Comput. Sci.\u00a0197(1\u20132), 95\u2013109 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"36_CR2","doi-asserted-by":"publisher","first-page":"890","DOI":"10.1016\/j.jcss.2005.05.008","volume":"72","author":"Y. Bartal","year":"2006","unstructured":"Bartal, Y., Bollob\u00e1s, B., Mendel, M.: Ramsey-type theorems for metric spaces with applications to online problems. J. Comput. Syst. Sci.\u00a072, 890\u2013921 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"36_CR3","doi-asserted-by":"publisher","first-page":"643","DOI":"10.4007\/annals.2005.162.643","volume":"162","author":"Y. Bartal","year":"2005","unstructured":"Bartal, Y., Mendel, M., Linial, N., Naor, A.: On metric Ramsey-type phenomena. Annals of Mathematics\u00a0162, 643\u2013710 (2005)","journal-title":"Annals of Mathematics"},{"key":"36_CR4","volume-title":"Online Computation and Competitive Analysis","author":"A. Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)"},{"key":"36_CR5","doi-asserted-by":"crossref","unstructured":"Borodin, A., Irani, S., Raghavan, P., Schieber, B.: Competitive paging with locality of reference. In: STOC, pp. 249\u2013259 (1991)","DOI":"10.1145\/103418.103422"},{"key":"36_CR6","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1145\/146585.146588","volume":"39","author":"A. Borodin","year":"1992","unstructured":"Borodin, A., Linial, N., Saks, M.E.: An optimal on-line algorithm for metrical task system. J. ACM\u00a039, 745\u2013763 (1992)","journal-title":"J. ACM"},{"issue":"1-2","key":"36_CR7","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/S0304-3975(98)00118-2","volume":"209","author":"D. Breslauer","year":"1998","unstructured":"Breslauer, D.: On competitive on-line paging with lookahead. Theor. Comput. Sci.\u00a0209(1-2), 365\u2013375 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"36_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/11523468_28","volume-title":"Automata, Languages and Programming","author":"R. Cohen","year":"2005","unstructured":"Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-guided graph exploration by a finite automaton. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 335\u2013346. Springer, Heidelberg (2005)"},{"key":"36_CR9","doi-asserted-by":"crossref","unstructured":"Chrobak, M., Larmore, L.L.: The server problem and on-line games. In: On-line algorithms: Proc. of a DIMACS Workshop. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a07, pp. 11\u201364 (1991)","DOI":"10.1090\/dimacs\/007\/02"},{"key":"36_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-540-77566-9_21","volume-title":"SOFSEM 2008: Theory and Practice of Computer Science","author":"S. Dobrev","year":"2008","unstructured":"Dobrev, S., Kr\u00e1lovi\u010d, R., Pardubsk\u00e1, D.: How much information about the future is needed? In: Geffert, V., Karhum\u00e4ki, J., Bertoni, A., Preneel, B., N\u00e1vrat, P., Bielikov\u00e1, M. (eds.) SOFSEM 2008. LNCS, vol.\u00a04910, pp. 247\u2013258. Springer, Heidelberg (2008)"},{"key":"36_CR11","unstructured":"Emek, Y., Fraigniaud, P., Korman, A., Ros\u00e9n, A.: On the additive constant of the k-server work function algorithm. A manuscript, \n                    \n                      http:\/\/arxiv.org\/abs\/0902.1378v1"},{"key":"36_CR12","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J. Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci.\u00a069, 485\u2013497 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"36_CR13","doi-asserted-by":"crossref","unstructured":"Fiat, A., Karlin, A.: Randomized and multipointer paging with locality of reference. In: STOC, pp. 626\u2013634 (1995)","DOI":"10.1145\/225058.225280"},{"key":"36_CR14","doi-asserted-by":"publisher","first-page":"1403","DOI":"10.1137\/S0097539700376159","volume":"32","author":"A. Fiat","year":"2003","unstructured":"Fiat, A., Mendel, M.: Better algorithms for unfair metrical task systems and applications. SIAM J. Comput.\u00a032, 1403\u20131422 (2003)","journal-title":"SIAM J. Comput."},{"key":"36_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/978-3-540-73420-8_22","volume-title":"Automata, Languages and Programming","author":"P. Fraigniaud","year":"2007","unstructured":"Fraigniaud, P., Gavoille, C., Ilcinkas, D., Pelc, A.: Distributed computing with advice: information sensitivity of graph coloring. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 231\u2013242. Springer, Heidelberg (2007)"},{"key":"36_CR16","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Korman, A., Lebhar, E.: Local MST computation with short advice. In: SPAA, pp. 154\u2013160 (2007)","DOI":"10.1145\/1248377.1248402"},{"key":"36_CR17","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Ilcinkas, D., Pelc, A.: Oracle size: a new measure of difficulty for communication tasks. In: PODC, pp. 179\u2013187 (2006)","DOI":"10.1145\/1146381.1146410"},{"key":"36_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/11821069_2","volume-title":"Mathematical Foundations of Computer Science 2006","author":"P. Fraigniaud","year":"2006","unstructured":"Fraigniaud, P., Ilcinkas, D., Pelc, A.: Tree exploration with an oracle. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol.\u00a04162, pp. 24\u201337. Springer, Heidelberg (2006)"},{"key":"36_CR19","unstructured":"Grove, E.F.: Online bin packing with lookahead. In: SODA, pp. 430\u2013436 (1995)"},{"key":"36_CR20","doi-asserted-by":"crossref","unstructured":"Fusco, E.G., Pelc, A.: Trade-offs between the size of advice and broadcasting time in trees. In: SPAA (2008)","DOI":"10.1145\/1378533.1378545"},{"key":"36_CR21","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0304-3975(97)00006-6","volume":"194","author":"S. Irani","year":"1998","unstructured":"Irani, S., Seiden, S.S.: Randomized algorithms for metrical task systems. Theor. Comput. Sci.\u00a0194, 163\u2013182 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"36_CR22","doi-asserted-by":"crossref","unstructured":"Korman, A., Kutten, S.: Distributed verification of minimum spanning trees. In: PODC, pp. 26\u201334 (2006)","DOI":"10.1145\/1146381.1146389"},{"key":"36_CR23","doi-asserted-by":"crossref","unstructured":"Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. In: PODC, pp. 9\u201318 (2005)","DOI":"10.1145\/1073814.1073817"},{"issue":"5","key":"36_CR24","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1145\/210118.210128","volume":"42","author":"E. Koutsoupias","year":"1995","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: On the k-server conjecture. J. ACM\u00a042(5), 971\u2013983 (1995)","journal-title":"J. ACM"},{"key":"36_CR25","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","volume":"11","author":"M.S. Manasse","year":"1990","unstructured":"Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for server problems. Journal of Algorithms\u00a011, 208\u2013230 (1990)","journal-title":"Journal of Algorithms"},{"key":"36_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/978-3-540-72951-8_6","volume-title":"Structural Information and Communication Complexity","author":"N. Nisse","year":"2007","unstructured":"Nisse, N., Soguet, D.: Graph searching with advice. In: Prencipe, G., Zaks, S. (eds.) SIROCCO 2007. LNCS, vol.\u00a04474, pp. 51\u201365. Springer, Heidelberg (2007)"},{"issue":"3","key":"36_CR27","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1016\/j.tcs.2005.03.015","volume":"340","author":"D. Peleg","year":"2005","unstructured":"Peleg, D.: Informative labeling schemes for graphs. Theor. Comput. Sci.\u00a0340(3), 577\u2013593 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"36_CR28","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. In: STOC, pp. 183\u2013192 (2001)","DOI":"10.1145\/380752.380798"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02927-1_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T12:10:15Z","timestamp":1558267815000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02927-1_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029264","9783642029271"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02927-1_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}