{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,12]],"date-time":"2026-11-12T13:40:00Z","timestamp":1794490800226,"version":"4.9.1"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319133492","type":"print"},{"value":"9783319133508","type":"electronic"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"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":[[2014]]},"DOI":"10.1007\/978-3-319-13350-8_20","type":"book-chapter","created":{"date-parts":[[2014,12,9]],"date-time":"2014-12-09T02:46:18Z","timestamp":1418093178000},"page":"264-276","source":"Crossref","is-referenced-by-count":3,"title":["A Technique to Obtain Hardness Results for Randomized Online Algorithms \u2013 A Survey"],"prefix":"10.1007","author":[{"given":"Hans-Joachim","family":"B\u00f6ckenhauer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Juraj","family":"Hromkovi\u010d","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dennis","family":"Komm","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2014,12,10]]},"reference":[{"key":"20_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-319-04298-5_8","volume-title":"SOFSEM 2014: Theory and Practice of Computer Science","author":"K Barhum","year":"2014","unstructured":"Barhum, K.: Tight Bounds for the Advice Complexity of the Online Minimum Steiner Tree Problem. In: Geffert, V., Preneel, B., Rovan, B., \u0160tuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 77\u201388. Springer, Heidelberg (2014)"},{"key":"20_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-319-04298-5_9","volume-title":"SOFSEM 2014: Theory and Practice of Computer Science","author":"K Barhum","year":"2014","unstructured":"Barhum, K., B\u00f6ckenhauer, H.-J., Fori\u0161ek, M., Gebauer, H., Hromkovi\u010d, J., Krug, S., Smula, J., Steffen, B.: On the Power of Advice and Randomization for the Disjoint Path Allocation Problem. In: Geffert, V., Preneel, B., Rovan, B., \u0160tuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 89\u2013101. Springer, Heidelberg (2014)"},{"key":"20_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/978-3-642-32241-9_44","volume-title":"Computing and Combinatorics","author":"MP Bianchi","year":"2012","unstructured":"Bianchi, M.P., B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Keller, L.: Online Coloring of Bipartite Graphs with and without Advice. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol. 7434, pp. 519\u2013530. Springer, Heidelberg (2012)"},{"key":"20_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-642-38768-5_7","volume-title":"Computing and Combinatorics","author":"MP Bianchi","year":"2013","unstructured":"Bianchi, M.P., B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Krug, S., Steffen, B.: On the Advice Complexity of the Online L(2,1)-Coloring Problem on Paths and Cycles. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 53\u201364. Springer, Heidelberg (2013)"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N., Buchbinder, N., Madry, A., Naor, J.: A polylogarithmic-competitive algorithm for the \n                      \n                        \n                      \n                      $$k$$\n                    -server problem (extended abstract). In: Proc. of FOCS 2011, pp. 267\u2013276 (2011)","DOI":"10.1109\/FOCS.2011.63"},{"key":"20_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/978-3-642-31644-9_2","volume-title":"Languages Alive","author":"H-J B\u00f6ckenhauer","year":"2012","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Komm, D., Kr\u00e1lovi\u010d, R., Rossmanith, P.: On the Power of Randomness versus Advice in Online Computation. In: Bordihn, H., Kutrib, M., Truthe, B. (eds.) Languages Alive. LNCS, vol. 7300, pp. 30\u201343. Springer, Heidelberg (2012)"},{"key":"20_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/978-3-642-38768-5_44","volume-title":"Computing and Combinatorics","author":"H-J B\u00f6ckenhauer","year":"2013","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Komm, D., Krug, S., Smula, J., Sprock, A.: The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 493\u2013505. Springer, Heidelberg (2013)"},{"key":"20_CR8","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.J., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: On the advice complexity of the \n                      \n                        \n                      \n                      $$k$$\n                    -server problem. In: Aceto, L., Henzinger, M., Sgall, J. (eds.): ICALP 2011, Part I. LNCS, vol. 6755, pp. 207\u2013218. Springer, Heidelberg (2011)","DOI":"10.1007\/978-3-642-22006-7_18"},{"key":"20_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-3-642-10631-6_35","volume-title":"Algorithms and Computation","author":"H-J B\u00f6ckenhauer","year":"2009","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R., M\u00f6mke, T.: On the Advice Complexity of Online Problems. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 331\u2013340. Springer, Heidelberg (2009)"},{"key":"20_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-642-29344-3_6","volume-title":"LATIN 2012: Theoretical Informatics","author":"H-J B\u00f6ckenhauer","year":"2012","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., Rossmanith, P.: On the Advice Complexity of the Knapsack Problem. In: Fern\u00e1ndez-Baca, D. (ed.) LATIN 2012. LNCS, vol. 7256, pp. 61\u201372. Springer, Heidelberg (2012)"},{"key":"20_CR11","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press (1998)"},{"key":"20_CR12","unstructured":"Boyar, J., Kamali, S., Larsen, K.S., L\u00f3pez-Ortiz, A.: Online bin packing with advice. In: Proc. of STACS 2014. LIPIcs 25, pp. 174\u2013186. Schloss Dagstuhl (2014)"},{"key":"20_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/978-3-319-04921-2_17","volume-title":"Language and Automata Theory and Applications","author":"J Boyar","year":"2014","unstructured":"Boyar, J., Kamali, S., Larsen, K.S., L\u00f3pez-Ortiz, A.: On the List Update Problem with Advice. In: Dediu, A.-H., Mart\u00edn-Vide, C., Sierra-Rodr\u00edguez, J.-L., Truthe, B. (eds.) LATA 2014. LNCS, vol. 8370, pp. 210\u2013221. Springer, Heidelberg (2014)"},{"key":"20_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1007\/978-3-642-35261-4_17","volume-title":"Algorithms and Computation","author":"R Dorrigiv","year":"2012","unstructured":"Dorrigiv, R., He, M., Zeh, N.: On the Advice Complexity of Buffer Management. In: Chao, K.-M., Hsu, T., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 136\u2013145. Springer, Heidelberg (2012)"},{"key":"20_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/978-3-642-38016-7_2","volume-title":"Approximation and Online Algorithms","author":"S Dobrev","year":"2013","unstructured":"Dobrev, S., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: Independent Set with Advice: The Impact of Graph Knowledge. In: Erlebach, T., Persiano, G. (eds.) WAOA 2012. LNCS, vol. 7846, pp. 2\u201315. Springer, Heidelberg (2013)"},{"key":"20_CR16","unstructured":"I. Seleceniova. Personal communication."},{"key":"20_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/978-3-642-31104-8_23","volume-title":"Structural Information and Communication Complexity","author":"S Dobrev","year":"2012","unstructured":"Dobrev, S., Kr\u00e1lovi\u010d, R., Markou, E.: Online Graph Exploration with Advice. In: Even, G., Halld\u00f3rsson, M.M. (eds.) SIROCCO 2012. LNCS, vol. 7355, pp. 267\u2013278. Springer, Heidelberg (2012)"},{"key":"20_CR18","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. 4910, pp. 247\u2013258. Springer, Heidelberg (2008)"},{"key":"20_CR19","unstructured":"Dohrau, J.: Online makespan scheduling with sublinear advice. Technical Report, ETH Zurich (2013)"},{"key":"20_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/978-3-642-02927-1_36","volume-title":"Automata, Languages and Programming","author":"Y Emek","year":"2009","unstructured":"Emek, Y., Fraigniaud, P., Korman, A., Ros\u00e9n, A.: Online Computation with Advice. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 427\u2013438. Springer, Heidelberg (2009)"},{"issue":"2","key":"20_CR21","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1109\/TIT.1975.1055349","volume":"21","author":"P Elias","year":"1975","unstructured":"Elias, P.: Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory 21(2), 194\u2013203 (1975)","journal-title":"IEEE Transactions on Information Theory"},{"key":"20_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-642-28332-1_20","volume-title":"Language and Automata Theory and Applications","author":"M Fori\u0161ek","year":"2012","unstructured":"Fori\u0161ek, M., Keller, L., Steinov\u00e1, M.: Advice Complexity of Online Coloring for Paths. In: Dediu, A.-H., Mart\u00edn-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 228\u2013239. Springer, Heidelberg (2012)"},{"key":"20_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-319-03578-9_5","volume-title":"Structural Information and Communication Complexity","author":"S Gupta","year":"2013","unstructured":"Gupta, S., Kamali, S., L\u00f3pez-Ortiz, A.: On Advice Complexity of the k-server Problem under Sparse Metrics. In: Moscibroda, T., Rescigno, A.A. (eds.) SIROCCO 2013. LNCS, vol. 8179, pp. 55\u201367. Springer, Heidelberg (2013)"},{"key":"20_CR24","unstructured":"Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics, 2nd ed. Addison-Wesley (1994)"},{"issue":"4","key":"20_CR25","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1137\/0405048","volume":"5","author":"JR Griggs","year":"1992","unstructured":"Griggs, J.R., Yeh, R.K.: Labelling graphs with a condition at distance \n                      \n                        \n                      \n                      $$2$$\n                    . SIAM Journal on Discrete Mathemtics 5(4), 586\u2013595 (1992)","journal-title":"SIAM Journal on Discrete Mathemtics"},{"key":"20_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-642-15155-2_3","volume-title":"Mathematical Foundations of Computer Science 2010","author":"J Hromkovi\u010d","year":"2010","unstructured":"Hromkovi\u010d, J., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: Information Complexity of Online Problems. In: Hlin\u011bn\u00fd, P., Ku\u010dera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 24\u201336. Springer, Heidelberg (2010)"},{"issue":"1","key":"20_CR27","first-page":"1","volume":"2","author":"J Hromkovi\u010d","year":"2007","unstructured":"Hromkovi\u010d, J., M\u00f6mke, T., Steinh\u00f6fel, K., Widmayer, P.: Job shop scheduling with unit length tasks: Bounds and algorithms. Algorithmic Operations Research 2(1), 1\u201314 (2007)","journal-title":"Algorithmic Operations Research"},{"key":"20_CR28","doi-asserted-by":"crossref","unstructured":"Komm, D., Kr\u00e1lovi\u010d, R.: Advice complexity and barely random algorithms. Theoretical Informatics and Applications (RAIRO) 45(2), 249\u2013267 (2011)","DOI":"10.1051\/ita\/2011105"},{"key":"20_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/978-3-642-30642-6_23","volume-title":"Computer Science \u2013 Theory and Applications","author":"D Komm","year":"2012","unstructured":"Komm, D., Kr\u00e1lovi\u010d, R., M\u00f6mke, T.: On the Advice Complexity of the Set Cover Problem. In: Hirsch, E.A., Karhum\u00e4ki, J., Lepist\u00f6, A., Prilutskii, M. (eds.) CSR 2012. LNCS, vol. 7353, pp. 241\u2013252. Springer, Heidelberg (2012)"},{"issue":"5","key":"20_CR30","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 \n                      \n                        \n                      \n                      $$k$$\n                    -server conjecture. Journal of the ACM 42(5), 971\u2013983 (1995)","journal-title":"Journal of the ACM"},{"key":"20_CR31","doi-asserted-by":"crossref","unstructured":"Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for on-line problems. In: Proc. of STOC 1998, pp. 322\u2013333 (1988)","DOI":"10.1145\/62212.62243"},{"key":"20_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/978-3-642-29116-6_17","volume-title":"Approximation and Online Algorithms","author":"MP Renault","year":"2012","unstructured":"Renault, M.P., Ros\u00e9n, A.: On Online Algorithms with Advice for the k-Server Problem. In: Solis-Oba, R., Persiano, G. (eds.) WAOA 2011. LNCS, vol. 7164, pp. 198\u2013210. Springer, Heidelberg (2012)"},{"key":"20_CR33","unstructured":"Renault, M.P., Ros\u00e9n, A., van Stee, R.: Online algorithms with advice for bin packing and scheduling problems. CoRR abs\/1311.7589 (2013)"},{"key":"20_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/978-3-642-38233-8_29","volume-title":"Algorithms and Complexity","author":"S Seibert","year":"2013","unstructured":"Seibert, S., Sprock, A., Unger, W.: Advice Complexity of the Online Coloring Problem. In: Spirakis, P.G., Serna, M. (eds.) CIAC 2013. LNCS, vol. 7878, pp. 345\u2013357. Springer, Heidelberg (2013)"},{"key":"20_CR35","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Probabilistic computations: Toward a unified measure of complexity (extended abstract). In: Proc. of FOCS 1977, pp. 222\u2013227. IEEE Computer Society (1977)","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Lecture Notes in Computer Science","Computing with New Resources"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13350-8_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T20:16:44Z","timestamp":1559074604000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-13350-8_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319133492","9783319133508"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13350-8_20","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-319-13350-8","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}