{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T23:01:13Z","timestamp":1773702073389,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662460771","type":"print"},{"value":"9783662460788","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-46078-8_15","type":"book-chapter","created":{"date-parts":[[2015,1,14]],"date-time":"2015-01-14T09:54:29Z","timestamp":1421229269000},"page":"177-188","source":"Crossref","is-referenced-by-count":8,"title":["Online Makespan Scheduling with Sublinear Advice"],"prefix":"10.1007","author":[{"given":"J\u00e9r\u00f4me","family":"Dohrau","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"15_CR1","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press (1998)"},{"key":"15_CR2","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.\u00a07936, pp. 493\u2013505. Springer, Heidelberg (2013)"},{"key":"15_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-642-22006-7_18","volume-title":"Automata, Languages and Programming","author":"H.-J. B\u00f6ckenhauer","year":"2011","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: On the advice complexity of the k-server problem. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol.\u00a06755, pp. 207\u2013218. Springer, Heidelberg (2011)"},{"key":"15_CR4","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.\u00a05878, pp. 331\u2013340. Springer, Heidelberg (2009)"},{"key":"15_CR5","unstructured":"Boyar, J., Kamali, S., Larsen, K.S., L\u00f3pez-Ortiz, A.: Online bin packing with advice. In: Proc.\u00a0of STACS 2014, pp. 174\u2013186 (2014)"},{"key":"15_CR6","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.tcs.2014.01.027","volume":"527","author":"H.-J. B\u00f6ckenhauer","year":"2014","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., Rossmanith, P.: The online knapsack problem: advice and randomization. Theoretical Computer Science\u00a0527, 61\u201372 (2014)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"15_CR7","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1145\/321356.321363","volume":"13","author":"G.J. Chaitin","year":"1966","unstructured":"Chaitin, G.J.: On the length of programs for computing finite binary sequences. Journal of the ACM\u00a013(4), 547\u2013569 (1966)","journal-title":"Journal of the ACM"},{"key":"15_CR8","unstructured":"Dohrau, J.: Online makespan scheduling with sublinear advice. Technical Report, ETH Zurich (2013)"},{"key":"15_CR9","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.\u00a05555, pp. 427\u2013438. Springer, Heidelberg (2009)"},{"key":"15_CR10","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.\u00a08179, pp. 55\u201367. Springer, Heidelberg (2013)"},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D.S. Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algoritms for scheduling problems: practical and theoretical results. Journal of ACM\u00a034, 144\u2013162 (1987)","journal-title":"Journal of ACM"},{"key":"15_CR12","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.\u00a06281, pp. 24\u201336. Springer, Heidelberg (2010)"},{"key":"15_CR13","first-page":"3","volume":"1","author":"A.N. Kolmogorov","year":"1965","unstructured":"Kolmogorov, A.N.: Three approaches to the definition of the concept \u201cquantity of information\u201d. Problemy Peredachi Informatsii\u00a01, 3\u201311 (1965)","journal-title":"Problemy Peredachi Informatsii"},{"key":"15_CR14","unstructured":"Komm, D.: Advice and randomization in online computation. PhD Thesis, ETH Zurich (2012)"},{"issue":"2","key":"15_CR15","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1051\/ita\/2011105","volume":"45","author":"D. Komm","year":"2011","unstructured":"Komm, D., Kr\u00e1lovi\u010d, R.: Advice complexity and barely random algorithms. Theoretical Informatics and Applications (RAIRO)\u00a045(2), 249\u2013267 (2011)","journal-title":"Theoretical Informatics and Applications (RAIRO)"},{"key":"15_CR16","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.\u00a07353, pp. 241\u2013252. Springer, Heidelberg (2012)"},{"key":"15_CR17","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":"M.P. 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.\u00a07164, pp. 198\u2013210. Springer, Heidelberg (2012)"},{"key":"15_CR18","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)"},{"issue":"1","key":"15_CR19","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/584091.584093","volume":"5","author":"C.E. Shannon","year":"2001","unstructured":"Shannon, C.E.: A mathematical theory of communication. Mobile Computing and Communications Review\u00a05(1), 3\u201355 (2001)","journal-title":"Mobile Computing and Communications Review"},{"issue":"2","key":"15_CR20","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Communications of the ACM\u00a028(2), 202\u2013208 (1985)","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2015: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-46078-8_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T23:59:47Z","timestamp":1559087987000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-46078-8_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662460771","9783662460788"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-46078-8_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}